[동적 계획법 1] [C++] 1463번. 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

해결 방법

우선 규칙을 찾아보자. 계산식의 경우 여러가지 경우의 수가 나올 수도 있다.

N	연산 횟수	계산식
1	1	1
2	1	2/2=1
3	1	3/3=1
4	2	(4-1)/3=1
5	3	(5-1)/2/2=1
6	2	6/3/2=1
7	3	(7-1)/3/2=1
8	3	8/2/2/2=1
9	2	9/3/3=1
10	3	(10-1)/3/3=1

어떤 규칙을 찾을 수 있을까?

우선 수가 1씩 커질 때마다 연산 횟수는 이전 값의 + 1을 해주면 될 것이다.

왜냐? '3번 규칙, 1을 뺀다'에 의해 '현재 자연수 - 1 = 이전 자연수(?)'이기 때문이다.

 

하지만 주의해야할 점이 있는데 바로 1, 2번 규칙에 해당할 때이다.

3이나 2로 나눠지는 경우의 최소 연산 횟수는 위에서 말한 방법이 아닌 3이나 2로 나누는 것이 더 적어지기 때문이다.

 

예를 들어 8의 경우 3번 규칙만 있다고 가정하면, 8-1-1-... = 1, 총 7번의 연산 과정이 필요하다.

하지만 8은 2로 나눠지므로 8/2/2/2 = 1, 총 3번의 연산으로도 1을 만들 수 있게 된다.

 

따라서 3으로 나눠지는 경우에는 '현재 자연수/3의 연산 횟수' + 1

2로 나눠지는 경우에는 '현재 자연수/2의 연산 횟수' + 1로 나타낼 수 있을 것이다.

 

우선 dp를 최소 연산 횟수를 저장할 배열이라고 생각하자.

이를 점화식으로 구현하면

dp[i] = dp[i-1] + 1, dp[i/3] + 1, dp[i/2] + 1 가 된다.

 

 

최종 코드는

 

#include <iostream>
using namespace std;

int min(int a, int b){
    return a < b ? a : b;
}

int main(){
    int n;
    cin >> n;
    
    int cnt[1000001];
    cnt[1] = 0;
    cnt[2] = 1;
    cnt[3] = 1;
    
    if (n >= 4){
        for(int i=4; i<=n; i++){
            cnt[i] = cnt[i-1] + 1;
            if(i%3 == 0){
                cnt[i] = min(cnt[i], cnt[i/3] + 1);
            }
            if(i%2 == 0){
                cnt[i] = min(cnt[i], cnt[i/2] + 1);
            }
        }
    }
    cout << cnt[n];
    return 0;
}

 

코드에서 cnt[2]와 cnt[3]을 초기화 해주었지만 저 과정은 생략해도 상관없다.

하지만 'cnt[1] = 0', 이 과정은 무조건 해줘야한다.

 

개인적으로 어려웠다...