[BOJ-1463][C++] 1로 만들기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (하단 참고)	128 MB	230137	75838	48572	32.294%

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

2

 

예제 출력 1 

1

 

예제 입력 2 

10

 

예제 출력 2

3

 

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

알고리즘 분류

• 다이나믹 프로그래밍

 

시간 제한

• Python 3: 1.5 초
• PyPy3: 0.7 초
• Python 2: 1.5 초
• PyPy2: 0.7 초

 

문제 출처

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

1463번: 1로 만들기

 

---

 

문제 해결 방법

• 시간 제한 0.15초의 문제로, DP를 이용하여 빠르게 문제를 해결할 수 있다.
• @dp[n]@은 @n@을 1로 만들 수 있는 연산 횟수의 최솟값이라고 가정한다.

 

점화식 구하기

• 우선, 문제에 주어진 가능한 연산은 다음과 같다.

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

• DP는 Bottom-Up 방식의 문제 해결 방법이므로, @n = 1@부터 @n = 3@까지 기본적인 값들을 미리 구해놓고 순차적으로 계산해본다.

dp[1] = 0;    // X
dp[2] = 1;    // [연산2]
dp[3] = 1;    // [연산1]

 

예 : 1부터 10까지의 최소 연산 횟수 구하기

• 문제에서 주어진 연산을 이용하여 최소의 연산 횟수를 구할 수 있는 경우를 살펴보면 다음과 같다. 
• @n = 1@일 때, @1@을 1로 만들 수 있는 최소의 연산은 없다.
  • 따라서 @dp[1] = 0@이다.
• @n = 2@일 때, @2@를 1로 만들 수 있는 최소의 연산은 다음과 같다.
  
  • [연산 2] (1가지)
  • @dp[2] = 1@
• @n = 3@일 때, @3@을 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  • [연산 1] (1가지)
  • @dp[3] = 1@
• @n = 4@일 때, @4@를 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 2] + [연산 2] (2가지)
  • [연산 3] + [연산 1] (2가지)
  • @dp[4] = 2@
• @n = 5@일 때, @5@를 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 3] + [연산 3] + [연산 1] (3가지)
  • [연산 3] + [연산 2] + [연산 2] (3가지)
  • @dp[5] = 3@
• @n = 6@일 때, @6@을 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 1] + [연산 2] (2가지)
  • [연산 2] + [연산 1] (2가지)
  • @dp[6] = 2@

• @n = 7@일 때, @7@을 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 3] + [연산 1] + [연산 2] (3가지)
  • [연산 3] + [연산 2] + [연산 1] (3가지)
  • @dp[7] = 3@

• @n = 8@일 때, @8@을 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 2] + [연산 2] + [연산 2] (3가지)
  • @dp[8] = 3@

• @n = 9@일 때, @9@를 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 1] + [연산 1] (2가지)
  • [연산 3] + [연산 2] + [연산 2] + [연산 2] (4가지)
  • @dp[9] = 2@
• @n = 10@일 때, @10@을 1로 만들 수 있는 최소의 연산은 다음과 같다. 
  
  • [연산 3] + [연산 1] + [연산 3] (3가지)
  • [연산 2] + [연산 3] + [연산 2] + [연산2] (4가지)
  • @dp[10] = 3@
• 표로 정리하면 다음과 같다.

n	dp[n] (최소 연산 횟수)
1	0
2	1
3	1
4	2
5	3
6	2
7	3
8	3
9	2
10	3

• 따라서 @dp[n]@에 다음의 두 연산 중 최솟값을 선택해주면 된다..

① @dp[n - 1]@ + 1 ② @dp[i / 2] + 1@ or @dp[i / 3] + 1@

• 이를 토대로 점화식을 구하면 다음과 같다.

$$dp[n] = \begin{cases} 0 &\text{(if   n = 1)} \\ \text{min}(dp[n], \; dp[n / 2] + 1) & (\text{if   n % 2 = 0}) \\  \text{min}(dp[n], \; dp[n / 3] + 1) & (\text{if   n % 3 = 0}) \\ dp[n - 1] + 1 & \text{Otherwise} \end{cases}$$

• 코드로 표현하면 다음과 같다.

int Solution(int n) {
    dp[1] = 0;   
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;  
        if (i % 2 == 0) {    // 2로 나누어 떨어질 경우
            dp[i] = min(dp[i], dp[i / 2] + 1);    
        }
        if (i % 3 == 0) {    // 3으로 나누어 떨어질 경우
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
    }
    return dp[n];
}

 

• 쉽게 이해해보자. @dp[4]@를 구한다고 해보자.
• @dp[4]@는 다음과 같이 2가지 방법으로 구할 수 있으며, 두 방법 중 최솟값을 선택해준다.
  • ① 방법 1 : @dp[n] = dp[n - 1] + 1@
    • @dp[4] = dp[4 - 1] + 1 = dp[3] + 1@
      • @dp[3] = dp[4] - 1@
        • 4를 구하는 최소 연산 횟수에서 연산 횟수 1을 빼주면 된다. (1을 빼준다. 즉, [연산 3] 수행)
        • 3을 1로 만드는 최소 연산 횟수는 4를 1로 만드는 최소 연산 횟수에서 1을 빼주면 된다.
          • dp[3] = 1 ([연산 1])
          • dp[4] = 2 ([연산 3] + [연산 1])
  • ② 방법 2 : @dp[n] = dp[n / 2(3)] + 1@
    • @dp[4] = dp[4 / 2] + 1 = dp[2] + 1@ (2로 나누어 떨어지는 경우)
      • @dp[2] = dp[4] - 1@
        • 4를 구하는 최소 연산 횟수에서 연산 횟수 1을 빼준다.(2로 나눠준다. 즉, [연산 2] 수행)
        • 2를 1로 만드는 최소 연산 횟수는 4를 1로 만드는 최소 연산 횟수에서 1을 빼주면 된다.
          • dp[2] = 1 ([연산 2])
          • dp[4] = 2 ([연산 2] + [연산 2])
    • @dp[4] = dp[4 / 3] + 1@ (3으로 나누어 떨어지는 경우)
      • @dp[4 / 3] = dp[4] - 1@
        • 4를 구하는 최소 연산 횟수에서 연산 횟수 1을 빼준다. (3으로 나눠준다. 즉, [연산 1] 수행)
• 즉, @n@이 @2@ 또는 @3@으로 나누어 떨어지면 @방법 ①@과 @방법 ②@를 모두 수행해야 하므로, @dp[n - 1] + 1@ 과 @dp[n / 2] - 1@ (또는 @dp[n / 3] + 1@)의 최솟값을 @dp[n]@으로 지정한다.
• 그렇지 않을 경우, @방법 ②@를 수행할 필요가 없으므로, @dp[n - 1] + 1@을 @dp[n]@으로 지정한다.

 

코드

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

int N;
int dp[1000001];

void Input() {
    cin >> N;
}

int Solution(int n) {
    dp[1] = 0;  
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) {    // 2로 나누어 떨어질 경우
            dp[i] = min(dp[i], dp[i / 2] + 1);    
        }
        if (i % 3 == 0) {    // 3으로 나누어 떨어질 경우
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
    }
    return dp[n];
}

void Output() {
    cout << Solution(N) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버III