이것이코딩테스트다2 [이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍 이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다. 문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다. 최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진.. 2024. 9. 6. [이것이 코딩 테스트다] 1로 만들기 - 다이나믹 프로그래밍 백준 1로 만들기와 같은 유형의 문제다.X에서 1로 만들기 방법이다. X에서 1로 한 번 순회한다.현재 위치 i (1에서 연산가능한 모든 숫자에 최소 연산 횟수를 기록한다.i가 1이 될 때까지 위 과정을 반복한다.# 1로 만들기X = int(input())dp = [10**8] * (X+1)dp[X] = 0for i in range(X, 0, -1): dp[i-1] = min(dp[i]+1, dp[i-1]) if i%2 == 0: dp[i//2] = min(dp[i]+1, dp[i//2]) if i%3 == 0: dp[i//3] = min(dp[i] + 1, dp[i//3]) if i%5 == 0: dp[i//5] = min(dp[i] + 1, .. 2024. 9. 5. 이전 1 다음