How We Coding

[1463] 1로 만들기

BOJ/DP2018. 1. 26. 11:24

http://boj.kr/1463


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 == 1return 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