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

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

1463번: 1로 만들기

 

[문제 설명]

 

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

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

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

 

[입력]

 

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

 

[출력]

 

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

 

[입출력 예제]

 

입력	출력
2	1
10	3

 

[문제 풀이]

dp문제를 거의 처음 풀기도 하는 거여서 점화식도 이렇게 세우는게 맞는지 고민했다.
일단 내 풀이를 공유하기 위해 적어본다.

우선 이 문제는 다이나믹 프로그래밍 문제로 점화식을 세워야 한다.
그래서 노트에 끄적거리며 점화식을 세웠다.

입력이 2로 들어왔을 때 1로 만들기 위해서는 2가지 케이스가 있다.
Case 1)
1. 2에서 1을 뺀다
연산 횟수 : 1
Case 2)
1. 2를 2로 나눈다.
연산 횟수 : 1
최종 연산 횟수 : 1

입력이 3으로 들어왔을 때 1로 만들기 위해서는 3가지 케이스가 있다.
Case 1)
1. 3에서 1을 뺀다.
2. 뺀 결과(2)에서 2로 나누어 준다.
연산 횟수 : 2
Case 2)
1. 3에서 1을 뺀다.
2. 뺀 결과(2)에서 1을 뺀다.
연산 횟수 : 2
Case 3)
1. 3을 3으로 나누어 준다.
연산 횟수 : 1
최종 연산 횟수 : 1

입력이 4로 들어왔을 때 1로 만들기 위해서는 2가지 케이스가 있다.
Case 1 )
1. 4에서 1을 뺀다.
2. 뺀 결과(3)를 3으로 나누어 준다.
연산 횟수 : 2
Case 2 )
1. 4를 2로 나누어 준다.
2. 나눈 결과(2)를 2로 나누어 준다.
연산 횟수 : 2
최종 연산 횟수 : 2

입력이 5로 들어왔을 때 1로 만들기 위해서는 1가지 케이스가 있다.
Case 1)
1. 5에서 1을 빼준다.
2. 뺀 결과(4)를 2로 나누어 준다.
3. 나눈 결과(2)를 2로 나누어 준다.
연산 횟수 : 3
최종 연산 횟수 : 3

입력이 6으로 들어왔을 때 1로 만들기 위해서는 2가지 케이스가 있다.
Case 1)
1. 6에서 2로 나누어 준다.
2. 나눈 결과(3)를 3으로 나누어 준다.
연산 횟수 : 2
Case 2)
1. 6에서 3으로 나누어 준다.
2. 나눈 결과(2)를 2로 나누어 준다.
연산 횟수 : 2
최종 연산 횟수 : 2

입력이 7로 들어왔을 때 1로 만들기 위해서는 1가지 케이스가 있다.
Case 1)
1. 7에서 1을 빼준다.
2. 뺀 결과(6)을 2로 나누어 준다.
3. 나눈 결과(3)을 3으로 나누어 준다.
연산 횟수 : 3
최종 연산 횟수 : 3

위 내용을 정리하면4가지 Case에 대해 점화식을 세울 수 있다.

👆 2로 나누어지면서 3으로 나누어 지는 Case
dp[n] = dp[n/2] + 1
dp[n] = dp[n/3] + 1
최소(min)을 구하면 된다.

👆 2로만 나누어지는 Case
dp[n] = dp[n-1] + 1
dp[n] = dp[n/2] + 1
최소(min)을 구하면 된다.

👆 3으로만 나누어지는 Case
dp[n] = dp[n/3] + 1
dp[n] = dp[n-1] + 1
최소(min)을 구하면 된다.

👆 2와 3 어느 것도 나누어지지 않는 Case
dp[n] = dp[n-1] + 1

그리고 입력 크기 + 1 만큼의 배열을 만들어서 각 입력에 대한 최소 연산을 저장했다.

이렇게 코드를 작성했을 때 시간은 0ms로 나왔다.

[최종 코드]

 

[GitHub]

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

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

int save[1000001] = { 0, };

int dp(int x) {
    if (x == 1) return 0;
    if ((x == 2) || (x == 3)) return 1;


    if (save[x] != 0) return save[x];


    if ((x % 2 == 0) && (x % 3 == 0)) {
        return save[x] = min(dp(x / 2) + 1, dp(x / 3) + 1);
    }
    else if (x % 2 == 0) {
        return save[x] = min(dp(x - 1) + 1, dp(x / 2) + 1);
    }
    else if (x % 3 == 0) {
        return save[x] = min(dp(x - 1) + 1, dp(x / 3) + 1);
    }
    else {
        return save[x] = dp(x - 1) + 1;
    }
}


int main() {
    int X;
    cin >> X;
    int result = dp(X);
    cout << result;
    return 0;
}