반응형
알고리즘 분류 : 다이나믹 프로그래밍
기초적인 DP문제이다. 3가지 조건을 따져서 점화식을 만들고, 이를 구현하면 된다.
- D[N] : N을 1로 만드는 최소 연산 횟수
- D[1] = 0
- D[N-1] + 1 : N에서 1을 뺀 경우
- D[N/3] + 1 : N을 3으로 나눈 경우
- D[N/2] + 1 : N을 2로 나눈 경우
C++ 소스코드
#include <cstdio> int d[1000001]; int solve(int n) { d[1] = 0; for (int i=2; i<=n; i++) { d[i] = d[i-1]+1; if (i%3 == 0) { int temp = d[i/3]+1; if (d[i] > temp) d[i] = temp; } if (i%2 ==0) { int temp = d[i/2]+1; if (d[i] > temp) d[i] = temp; } } return d[n]; } int main() { int n; scanf("%d", &n); printf("%d\n", solve(n)); return 0; }
Python 3 소스코드
def solve(n): d = [0]*(n+1) for i in range(2, n+1): d[i] = d[i-1]+1 if i%3 == 0: temp = d[i//3]+1 d[i] = min(d[i], temp) if i%2 == 0: temp = d[i//2]+1 d[i] = min(d[i], temp) print(d[n]) solve(int(input()))
참고
- 백준 온라인 저지 : BOJ 1463
반응형