백준(S3) 1463번: 1로 만들기 (C 언어 C11 C99)

코드를 보기 전에: 이 문제도 DP문제다. 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.  

이렇게 연산을 계속해서 1을 만들어야한다.

 

우선은 반복문을 만들어준다.

반복문 첫 문장이 dq[i]의 값이 전 값에서 1을 더한 것이므로 반복문은 2부터 시작한다.

for (int i = 2; i <= num; i++) 
        dp[i] = dp[i - 1] + 1;

배열에서 dp[i -1]인덱스에서 1을 더 한값과 i를 2로 나눈 숫자가 저장된 값을 비교해서 더 작은값을 고른다.

if (i % 2 == 0)
        {
           dp[i] = (MIN(dp[i], dp[i / 2] + 1));
        }

배열에서 dp[i-1]인덱스에서 1을 더한 값과 i를 3로 나눈 숫자가 저장된 값을 비교해서 더 작은 값을 고른다.

 

if (i % 3 == 0)
        {
            dp[i] = (MIN(dp[i], dp[i / 3] + 1)); 
        }

 

 

Fullcode

#include <stdio.h>
#define MIN(a,b) a<b?a:b
    int dp[1000001]; 
int main()
{
    int num;
    scanf("%d", &num);
    for (int i = 2; i <= num; i++)
    {
        dp[i] = dp[i - 1] + 1; 
        if (i % 2 == 0)
        {
            dp[i] = (MIN(dp[i], dp[i / 2] + 1));
        }
        if (i % 3 == 0)
        {
            dp[i] = (MIN(dp[i], dp[i / 3] + 1)); 
        }
    }
    printf("%d", dp[num]);
}