[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