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

안녕하세요.

오늘은  백준 1463번: 1로 만들기(링크)  문제를 풀어보려고 합니다.

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력

//case 1
2

//case 2
10

 

예제 출력

//case1
1

//case2
3

 

제한

시간 제한: 0.15초

메모리 제한: 128MB

 

---

풀이

 

[틀린 풀이]

해당 문제를 풀 때 저는 먼저 그리디로 접근 했었습니다.

1번 연산이 가장 많이 사용되어야 최솟값이 되고, 그 다음 2번, 3번 순서대로 사용되어야 한다고 가정한 것입니다.

 

그래서 1번 연산이 가능한 순간에는 무조건 1번 연산을 시행하고, 그 다음 2번을 시행하도록 코드를 작성했습니다.

#include <stdio.h>

int main(void)
{
	int x, count = 0;
	scanf("%d", &x);
	while (1)
	{
		if (x == 1)
			break;
		if (x % 3 == 0)
			x = x / 3;
		else if (x % 2 == 0)
			x = x / 2;
		else
			x = x - 1;
		count++;
	}
	printf("%d", count);
	return 0;
}

 

위 코드를 제출하면 당연히 틀렸습니다가 나옵니다. 반례는 아래와 같습니다.

 

입력: 16

출력: 5

정답: 4

---

 

[올바른 풀이]

이 문제는 그리디가 아닌 DP로 풀어야 합니다. 위에서와 같이 어떤 연산을 써야 최적해가 나오는지는 알 수 없기 때문입니다.

저는 bottom-up 방식으로 풀었습니다.

 

1) dp 정의

DP를 풀 때는 dp배열을 만들고, 해당 배열이 어떤 것인지 정의를 해줘야합니다.

 

dp[n] = n을 1로 만들기 위해 사용되는 최소 연산 횟수

 

2) 메모이제이션

위와 같이 dp 배열을 정의한 후에는, 이전 dp값(dp[1]~dp[n-1])을 가지고 dp[n]을 만드는 법을 생각해야 합니다.

 

1. 3번 연산

 

3번 연산을 먼저 생각해봅시다.

 

정수 n에 3번 연산을 시행하면 n-1이 됩니다.

그렇다면 우리가 구하려는 총 연산 횟수는 1 + (n-1을 1로 만드는 연산 횟수)라고 말할 수 있습니다.

 

그런데 우리가 원하는 값은 "최솟값"입니다.

1은 상수이므로 (n-1을 1로 만드는 연산 횟수)가 최솟값이 되어야 합니다.

 

위에서 정의한 dp[n]에 따르면 dp[n-1] = n-1을 1로 만드는 최소 연산 횟수가 됩니다.

 

즉, n에 3번 연산을 시행했을 때의 최소 연산 횟수는 dp[n] = dp[n-1] + 1

 

 

 

2. 1번, 2번 연산

 

1번, 2번 연산은 각각 3, 2로 나누어 떨어지는 경우에만 가능하니 아래와 같이 적을 수 있습니다.

 

1번 연산: dp[n] = dp[n/3] + 1, if n%3==0

2번 연산: dp[n] = dp[n/2] + 1, if n%2==0

 

 

3. dp[n]

이제 우리는 1번, 2번, 3번 연산의 각 dp값 중 최솟값을 구합니다.

 

즉, min(dp[n/3]+1, dp[n/2]+1, dp[n-1]+1)

 

위 내용을 토대로 dp[1]부터 dp[n]까지 차례대로 구하면 됩니다.

이 때 dp[1] = 0으로 미리 구해놓고 시작합니다.

 

 

정답

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

int main() {
	int n, dp[1000001];
	cin >> n;
	dp[1] = 0;
	for(int i=2; i<=n; i++){
		dp[i] = dp[i-1]+1;
		if(i%2==0)
			dp[i] = min(dp[i],dp[i/2]+1);
		if(i%3==0)
			dp[i] = min(dp[i],dp[i/3]+1);
	}
	cout << dp[n];
	return 0;
}

---

이렇게 해서 백준 1463번 1로 만들기 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!