[1463] 1로 만들기
BOJ/DP2018. 1. 26. 11:24
DP1 - basic
- go(n) : 3개의 연산을 적절히 사용했을 때, n을 1로 만드는 회수의 최소값.
< 소스코드 - top down >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> #define INF 0x3f3f3f3f int d[1000001]; int go(int n) { int a, b, c, ans; a = b = c = INF; if(n == 1) return 0; if(d[n]) return d[n]; if(n%3 == 0) a = go(n/3)+1; if(n%2 == 0) b = go(n/2)+1; c = go(n-1)+1; ans = a < b ? a : b; ans = ans < c ? ans : c; return d[n] = ans; } int main() { int n; scanf("%d", &n); printf("%d\n", go(n)); return 0; } | cs |
< 소스코드 - bottom up >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <stdio.h> int main() { int i, n, d[1000001]; scanf("%d", &n); d[1] = 0; for(i=2; i<=n; i++) { d[i] = d[i-1] + 1; if(i%2 == 0 && d[i] > d[i/2]+1) d[i] = d[i/2]+1; if(i%3 == 0 && d[i] > d[i/3]+1) d[i] = d[i/3]+1; } printf("%d\n", d[n]); return 0; } | cs |
-
'BOJ > DP' 카테고리의 다른 글
[2302] 극장 좌석 (0) | 2018.02.05 |
---|---|
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1149] RGB 거리 (0) | 2018.01.30 |