백준 1463번: 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

이 문제는 다이나믹 프로그래밍 문제로 큰문제를 작은 문제로 나누어서 풀면 된다 즉 n짜리 문제를 n-1짜리로 n-2 짜리로 ... 짜리로 나누어서 작은 문제로 푸는 것이다.

이 문제는 세가지 연산이 가능하다

n이 3으로 나누어 떨어질때 3으로 나눈다. 즉 d[n]=d[n/3]+1

n이 2로 나누어 떨어질때 2로 나눈다      d[n]=d[n/2]+1

n에 1을 뺀다     d[n]=d[n-1]-1

 

즉 이 세가지 중에서 최솟값을 구하면 된다.

 

이 문제를 풀 때 재채점이 되었고 틀리게 나왔다. 그 이유는 3으로 나누는게 2로 나누는 것보다 무조건 최솟값이라고 생각을 했기 떄문이다. 하지만 이는 잘못된 생각이었다. 값이 커짐에 따라 2로 나누어져서 가는게 더 빠른길이 나올 수도 있다. 그래서 이 생각을 고치고 다시 풀고 맞추었다. 코드를 보자

#include <iostream>
#include <vector>
using namespace std;
vector<int> d;
int main(){
    int n;
    cin >> n;
    for(int i=0; i<=n;i++){
        d.push_back(i-1);
    }
    for(int i=2;i<=n;i++){
        d[i]=d[i-1]+1;                    //일단 모두 1을 뺸다 어차피 대소비교할때 지장없음
        if((i%3)==0&&d[i]>d[i/3]+1){     //3으로 나누어지면 그리고 i값이 i/3에서 1더한것보다 크면
            d[i]=d[i/3]+1;
        }
        if((i%2)==0 && d[i]>d[i/2]+1){     //2로 나누어지면
            d[i]=d[i/2]+1;
        }
    }
    cout << d[n];
}