'DynamicProgramming' 태그의 글 목록
본문 바로가기
728x90

DynamicProgramming5

백준 No.17070 [파이프 옮기기 1] No.17070 [파이프 옮기기 1] 문제 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 설명 동적할당(DP : Dynamic programming) 을 이용하여 풀 수 있는 문제이다. 점화식을 위한 dp 배열은 3차원으로 선언을 하였다. dp[ i ][ j ][ k ] == (i, j) 좌표로 오는 파이프가 k 방향에서 올 수 있는 경우의 수 (k == 1 인 경우는 좌측, k == 2 인 경우는 위, k == 3 인 경우는 .. 2021. 8. 8.
백준 No.12015 [가장 긴 증가하는 부분 수열 2] Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2] 문제 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 설명 2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열] 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가.. 2021. 7. 28.
백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li.. 2021. 7. 28.
백준 No.1328 [고층 빌딩] Baekjoon Online Judge No.1328 [고층 빌딩] 문제 1328번: 고층 빌딩 (acmicpc.net) 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 설명 핵심 변수 : unsigned long long city[N][L][R]; N개의 빌딩이 있고, 좌측에서는 L 개의 빌딩, 우측에서는 R 개의 빌딩이 보일 때 경우의 수의 값을 의미한다. city[1][1][1] 은 1개의 빌딩이 있고, 좌측에서는 1개의 빌딩, 우측에서는 1개의 빌딩이 보이는 경우의 수의 값을 의미한다. 이 경우엔 그냥.. 2021. 7. 12.
백준 No.1937 [욕심쟁이 판다] Baekjoon Online Judge No.1937 [욕심쟁이 판다] 문제 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 설명 DFS를 활용한 DP문제이다. land[i][j] array 를 입력되는 대나무 숲에 대한 정보이고, dp[i][j] array 를 (i, j) 위치에서 최대로 살 수 있는 일수라고 하자. 백준 사이트에 있는 입력 예시이다. 한 위치를 예로 설명을 해 볼 것이다. 위 경우를 가지고 dp[0][1]의 값을 구하는 과정, 식은 아래와 같다. dp[0][1] = max(dp[0.. 2021. 7. 11.
728x90