[백준 1463] 1로 만들기 (DP, 점화식)
https://www.acmicpc.net/problem/1463
DP를 이해한 뒤에 처음 풀어보는 DP문제였다.
혼자 이해하는데도 시간이 오래걸렸던 문제라서 최대한 이해하기 쉽게 정리해두려고한다!
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제
2 입력 >> 1 출력
10 입력 >> 3 출력
예제에서 10을 입력했을 때 3이 출력되는 모습을 설명하자면, 3가지 규칙을 사용하여
10 - 5 - 4 - 2 - 1 로 총 4가 나올 것 같지만, 10을 입력했을 때 출력되는 값은 3이다.
10 - 9 - 3 - 1 으로 3을 최솟값인 3을 출력하게 된다.
이렇게 입력받은 정수에 3가지 규칙을 적절하게 사용하여 1을 만드는 최솟값을 구하는 문제이다.
또한 DP를 설명했던 이전 글에서처럼 최소값(최대값)이 갱신되면 이전의 값을 메모리에서 삭제한다는 점이 DP 알고리즘을 이용할 수 있다는 것을 예측해볼 수 있다.
위의 문제에서 각각의 정수값에 따른 값들을 저장하는데 있어서, 배열을 사용한다.
이때 배열의 이름을 dp로 하고, 배열 dp의 인덱스는 입력된 정수값을 의미한다.
그럼 dp[1]부터 차례대로 규칙성을 찾아보자!
dp[1]은 1을 입력받았을 때인데, 문제에서 요구하는 숫자가 바로 1이고 더 이상 연산할 필요가 없으므로
dp[1] = 0이다.
dp[2]는 2를 입력받았을 때, 2/2 또는 2-1의 연산을 통해 1로 만들 수 있는데, 이 두 가지 경우 모두 연산횟수가 1이므
dp[2] = 1이다.
dp[3]은 3을 입력받았을 때, 3/3 연산을 통해 1로 만들 수 있으므로
dp[3] = 1이다.
dp[4]는 4를 입력받았을 때, 4/2/2 또는 (4-1)/1 을 통해 1로 만들 수 있고, 이 두 가지 경우 모두 연산횟수가 2이므로
dp[4] = 2이다.
dp[5]는 5를 입력받았을 때, (5-1)/2/2 을 통해 1로 만들 수 있으므로
dp[5] = 3이다.
여기서, dp[4]의 경우와 dp[5]의 경우를 다시 살펴보자.
dp[4] = 4 / 2 / 2
dp[5] = (5-1)/ 2 / 2
2로도, 3으로도 나누어지지않는 5는 '5-1'을 통해 '4'가 되고, dp[4]의 연산이 똑같이 뒤따른다.
반대로 말하자면, dp[5]는 dp[4]의 최솟값에서 연산카운트를 '+1'을 한것과 같은 최솟값을 가진다.
따라서,
2와 3으로 나누어지지 않는 정수 i에 대하여 dp[i] = dp[i-1] + 1 (1번 점화식)
이 성립한다.
이어서 확인해보자면,
dp[6]은 6을 입력받았을 때, 6/3/2를 통해 1로 만들 수 있으므로
dp[6] = 2이다.
dp[7]은 7을 입력받았을 때, (7-1)/3/2 를 통해 1로 만들 수 있으므로
dp[7] = 3이다.
dp[6]과 dp[7]의 경우, 7은 2와3으로 나누어지지 않는 수이며, dp[7] = dp[6] + 1 을 만족한다.
이번에는 비슷하지만 조금 다른 경우인데,
dp[8]은 8/2/2/2 총 3번을 통해 1로 만들 수 있으므로, dp[8] = 3이다.
이때, 8/2/2/2 를 (8/2)/2/2로도 볼 수 있는데, 이는 (4)/2/2 즉 dp[4]+1로 볼 수 있다.
dp[9]는 9/3/3 총 2번을 통해 1로 만들 수 있으므로, dp[9] = 2이다.
이때, 9/3/3 을 (9/3)/3으로도 볼 수 있는데, 이는 (3)/3 즉 dp[3]+1로 볼 수 있다.
따라서,
2로 나누어떨어지는 정수 i에 대해 dp[i] = dp[i/2] + 1 이 성립하고 (2번 점화식)
3으로 나누어떨어지는 정수 i에 대해 dp[i] = dp[i/3] + 1이 성립한다. (3번 점화식)
위와 같은 2개의 점화식을 추가로 찾을 수 있다!
(설명하지 않고 넘어갔지만, dp[4] 또한 4/2/2를 (4/2)/2로 바꿀 수 있고, 이는 (2)/2이므로 dp[2]+1과 같다.
이런식으로 입력받은 모든 정수값을들 dp[i] + 1의 형태로 바꿀 수 있다!!)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int n;
int dp[1000001] = { 0, }; //입력조건이 1보다 크거나 같고 10^6보다 작거나 같은 정수 N
scanf("%d", &n);
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 3 == 0) {
if (dp[i] > dp[i / 3] + 1) //같은 값인 경우는 else로 넘어가서 값에 영향x
dp[i] = dp[i / 3] + 1;
//C++일때, dp[i] = min(dp[i / 3] + 1, dp[i]);
}
if (i % 2 == 0) {
if (dp[i] > dp[i / 2] + 1)
dp[i] = dp[i / 2] + 1;
//C++일때, dp[i] = min(dp[i / 2] + 1, dp[i]);
}
//2와 3으로 모두 나누어지는 경우는 i%3==0일때 dp[i]값과 i%2==0일때 dp[i]값이 비교되므로 따로 정리할 필요는 없다.
}
printf("%d", dp[n]); return 0;
}
|
cs |
소스코드의 전체적인 흐름을 살펴보면,