[백준] 1463 1로 만들기 C++(DP)

백준 1463 1로 만들기
https://www.acmicpc.net/problem/1463

정수 N을 입력했을 때 N을 1로 만들기 위해 필요한 최소한의 연산 횟수를 출력하는 문제이다. (N은 1보다 크거나 같다.)

문제의 조건을 보면
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이게 무슨 말이냐

• 1은 그대로 둬도 1이니까 => 0
• 2를 1로 만드려면
  • 2/2 => 1 (1이 1이되는 횟수 +1)
  • 2-1 => 1 (1이 1이되는 횟수 +1)
• 3을 1로 만드려면
  • 3/3 => 1 (1이 1이되는 횟수 +1)
  • (3-1)/2 => 2 (2가 1이되는 횟수 +1)
• 10을 1로 만드려면
  • (10/2-1)/2/2 => 4 (8이 1이 되는 횟수 +1)
  • (10-1)/3/3 => 3 (9가 1이 되는 횟수 + 1)

점화식은 다음과 같다.
d[i] = d[i/3] + 1;
d[i] = d[i/2] + 1;
d[i] = d[i-1] + 1;
가장 작은 연산 횟수를 구하려면
n이 들어왔을 때 세 가지 방법 중 가장 작은 값이 나오는 방법을 선택해야 하므로
세 가지 모두 적용해보고 비교연산을 해야한다. -> min() 사용

min(A,B)

• A와 B 중 작은 값 리턴
• algorithm 헤더에 포함되어 있음

*1을 더해주는 이유? - /3, /2, -1 의 연산을 했기 때문에 +1 해주는 것

DP는 bottom-up 방식이다.
bottom-up이란 기본적인 값들은 미리 구해놓고 순차적으로 계산하는 것이다.
그래서 기본적인 값들을 구해놓고 시작하자.
d[1] = 0;
d[2] = 1;
d[3] = 1;

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int N;
    scanf("%d",&N);
    int dp[10000001];

    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for(int i=4; i<=N; 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\n",dp[N]);
    return 0;
}

동적프로그래밍은 큰 문제를 작은 문제로 나누어 답을 구하는 방법이다.
작은 문제의 상태를 알아야 하기 때문에 보통 몇 가지 예시를 직접 테스트하는 경우가 많다.