BOJ [C++]) 1463번 1로 만들기

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

1463번: 1로 만들기

 

 

1. 문제 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

2. PS

- DP를 이용. 보텀업 방식을 취해줌.

- 2로 나누어 떨어진다면 2로 나눈 경우와 1을 빼주는 경우 중 최소 값, 3으로 나누어 떨어진다면 3으로 나눈 경우와 1을 빼주는 경우 중 최소값을 dp테이블에 메모함.

- 처음 실수한 부분은 2와3 둘다 나누어 지는 경우에 대해 최소값을 찾아주지 않아서 오답처리되었음.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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