반응형 DP38 백준 14462번 소가 길을 건너간 이유 8 - C++(cpp) 풀이 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 2. dp(l, r) = left_cows[l...]과 right_cows[r...] 사이에 놓을 수 있는 횡단보도의 최대 개수 3. dp(l, r) = max(왼쪽의 l번째 소는 연결하지 않는 경우, 왼쪽의 l번째 소와 오른쪽의 i번째 소와 연결하는 경우) 1. 왼쪽 목초지의 i번째 소를 연결하는 경우, 오른쪽 소 중 가장 앞쪽에 있는 소와 연결하는 것이 최적이다. 왼쪽 목초지의 소를 기준으로 차례로 연결한다고 하면, 횡단보도가 겹치지 않기 위해서는 연결시키는 오른쪽 목초지의 소도 오름차순이어야 한다. 즉, 더 나중에 매칭하는 오른쪽 소의 번호가 작아지면 안 된다. 이전 매칭에서 최대한 앞쪽의.. 2022. 4. 17. 백준 1099번 알 수 없는 문장 - C++(cpp) 풀이 1. dp(idx): 부분 문자열 sentence[idx...]를 해석하는 최소 비용 2. dp(idx) = min(앞부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size())) 3. 단어 매칭 비용 계산도 메모이제이션하여 시간을 절약한다. 1. dp(idx): 부분문자열 sentence[idx...]를 해석하는 최소 비용 앞부분을 어느 단어와 매칭 시키느냐에 따라 뒷부분을 해석하는 비용이 달라지므로 다이나믹프로그래밍을 사용하여 구할 수 있다. dp(idx)를 위와 같이 정의하면, 총 구해야 하는 dp값은 문장의 길이와 같으므로 총 N=50개가 된다. 2. dp(idx) = min(앞 부분을 단어 word에 매칭 하는 비용 + dp(idx+word.size())) 앞 부분을 단어로 매.. 2022. 4. 13. 백준 13398번 연속합 2 - C++(cpp) 풀이 1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합 2. dp[idx][1] = max(arr[i], arr[i]+dp[i+1]) 3. dp[idx][0] = max(arr[i], arr[i]+dp[i+1][0], arr[i]+dp[i+2][1]) 1. dp[idx][did_remove] = 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합 연속합은 재귀적으로 생각할 수 있다. 또한 숫자를 최대 한 개까지 제거할 수 있으므로 dp[idx][did_remove]를 숫자 제거 여부가 did_remove일 때 idx번째 수로 시작하는 최대 연속합이라고 정의하자. 2. dp[idx][1] = max(arr[i.. 2022. 4. 8. 백준 5557번 1학년 - C++(cpp) 풀이 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 2. dp(val, idx) = dp(val+arr[idx], idx+1) + dp(val-arr[idx], idx+1) 이다. 3. 최종적으로 구해야하는 값은 dp(arr[0], 1)이다. 1. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수~마지막 수까지 고려할 때 만들 수 있는 등식의 수라고 하자. 백트래킹으로 풀이하게되면, 최대 2^98번을 탐색하므로 시간초과가 발생한다. 중간 계산값이 0 이상 20 이하로 제한되어 있으므로 DP를 이용해서 풀이할 수 있다. dp(val, idx)를 현재까지의 계산값이 val이고 idx번째 수부터 고려할 때 .. 2022. 4. 6. 백준 22968번 균형 - C++(cpp) 풀이 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-1) + f(h-2) + 1 3. f(h) ≤ V인 h 중 최댓값을 찾는다. 1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자. AVL 트리에서는 모든 부분 트리가 AVL 트리이다. 따라서 재귀적인 방법을 떠올릴 수 있다. 먼저 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값을 f(h)라고 정의하자. 2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-.. 2022. 4. 1. 이전 1 2 3 4 5 6 7 8 다음 반응형
