[C++]백준 - 1463번 문제

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

1463번 : 1로 만들기

---

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

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

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

 

입력

---

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

출력

---

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

 

 

 

 

---

 

생각해 볼 점

---

문제에 나온대로 쉽게 점화식을 구할 수 있습니다.

 

x(n) = { if(n == 1) 1,

           if(n > 1) min( x( n / 2 ), x( n / 3 ), x( n - 1)) + 1}

 

위의 점화식을 사용하면 쉽게 동적계획법으로 코딩을 할 수 있습니다.

 

코드

---

#include <iostream>
using namespace std;
int dp[1000001] = {0,};  

int solution(int N) 
{
    if(N == 1) return 0;
    if(dp[N] != 0) return dp[N];
    
    //3으로 나눔, 2로 나눔, -1을 함
    int min = solution(N-1);
    if(N % 3 == 0) 
    {
        int three = solution(N / 3);
        if(three < min) min = three;
    }
    if(N % 2 == 0)
    {
        int two = solution(N / 2);
        if(two < min) min = two;
    }
    dp[N] = min + 1;
    return dp[N];
}


int main() 
{
    int N;
    cin >> N;
    cout << solution(N);
	return 0;
}

 

그 외

---