1463번: 1로 만들기(백준 C++)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

코드

#include <iostream>
using namespace std;

int n;
int dp[1000001];
//각 숫자별 1이 될 때까지 수행해야하는 최소 단계 저장.

int min(int a, int b){
	return a < b ? a : b;
}

void solve(){
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	
	for(int i=4; i<=n; i++){
		if(i % 2 == 0 && i % 3 == 0){
			// i가 2의 배수이자 3의 배수인 경우
			dp[i] = min(min(dp[i / 2] + 1, dp[i / 3] + 1), dp[i - 1] + 1);
		}
		else if(i % 2 == 0){
			// i가 2의 배수인 경우
			dp[i] = min(dp[i / 2] + 1, dp[i - 1] + 1);
		}
		else if(i % 3 == 0){
			// i가 3의 배수인 경우
			dp[i] = min(dp[i / 3] + 1, dp[i - 1] + 1);
		}
		else{
			// i가 2의 배수도 3의 배수도 아닌 경우, (-1)
			dp[i] = dp[i-1] + 1;
		}
	}
	cout << dp[n];
}

int main() {
	cin >> n;
	solve();
	return 0;
}

 

문제

동적계획법, 즉 DP를 사용하여 푸는 문제입니다.

주어진 수 N을 3가지 연산을 활용하여 1로 만드는데 연산횟수가 최소로 될 때의 횟수가 몇인지 찾는 문제입니다.

연산 방법에는

1) 2로 나누어진다면 2로 나눈다.

2) 3으로 나누어진다면 3으로 나눈다.

3) 1로 뺀다.

 

제 개인적인 생각으로 DP문제에 접근할때는 문제가 주는 방향의 반대로 거슬러 간다.

라고 접근하시는 편이 풀이에 용이한 것 같습니다.

무슨 의미인지 밑에서 예시를 통해 설명해 보겠습니다.

 

풀이

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

위의 예제를 통해 알아 보겠습니다.

우선, 그전에

 

1이 1이 되기위해선 연산이 몇 번 필요할까요?

0번 필요합니다.

그렇다면 2와 3이 1이 되기위해선 몇 번 필요할까요?

각각 2 또는 3으로 나누어 주면 되므로 1번 필요합니다.

 

그러므로 각 수마다 연산에 필요한 수를 담는 DP 배열의 초기값은 아래와 같습니다.

 

그렇다면 4부터 10까지 차근차근 연산의 최소 횟수를 구하면서 알아보도록 하겠습니다.

N = 4

4는 2로 나누어지는 수 입니다.

따라서 주어진 연산하에서  4가 1에 가까워지는  방법에는 2로 나누거나, 1을 빼는 방법이 있겠습니다.

1) 2로 나누는 경우

4를 2로 나누어서 2가 됩니다.

그런데 이미 저희는 DP[2] 의 값을 알고 있죠, 1입니다.

이미 2에서 1이 되는 최소값은 알고 있으므로 그 최소값에 4에서 2로 가는 연산횟수 1을 추가해서

DP[4]는 2가 됩니다.

 

2) 1을 빼는 방법

1)과 마찬가지입니다. 1을 빼면 3이되고

우리는 DP[3]의 값을 알고 있으므로 1을 빼는연산횟수인 1을 DP[3]에 추가한 수인 2가

DP[4] 가 되는 것입니다.

 

그렇다면 이제 1)과 2)의 값을 비교해서 더 작은 값을 DP[4] 에 저장하면됩니다.

이 경우에는 둘 다 2로 동일하므로 DP[4]는 2가 되겠습니다.

 

 

N = 5

5는 2로도, 3으로도 나누어지지 않는 수입니다.

그렇기 때문에 5에서 4로 가는 방법 하나 밖에 존재하지 않죠.

그렇기 때문에 기존 DP[4]의 값에서 + 1 된 값이 DP[5]가 되겠습니다.

 

N = 6

6은 2로도 3으로도 나누어지는 수입니다.

그렇기 때문에 3가지 방법을 다 고려해서 최소값을 찾아야합니다.

1) 2로 나누어지는 경우

DP[6] = DP[3] + 1 = 2

2) 3으로 나누어지는 경우

DP[6] = DP[2] + 1 = 2

3) 1을 빼는 경우

DP[6] = DP[5] + 1 = 4

3가지 방법 중 최소값은 2로, DP[6] 은 2가 되겠습니다.

 

이제 점화식이 눈에 들어오실거라고 생각됩니다.

그럼 빠르게 설명을 빼고 결과만 보도록 하겠습니다.

 

N = 7

 

N = 8

 

N = 9

 

N = 10

 

이렇게 해서 10이 1이 되는 연산의 최소 횟수는 3임을 알 수 있습니다.

 

즉 주어진 수 10부터 시작해서 1로 가는것이 아닌,

1부터 시작해서 각 수의 최소값에다가 +1 하고, 연산방법에 따라 어느 연산이 더 효율적인지 비교해가며 10에 도달했을때의 연산의 최소값을 출력하게 됩니다.