[백준 / BOJ] C++ 1463 1로 만들기

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

1463번: 1로 만들기

문제

 

풀이

문제에서 주어지는 조건은 3가지이다.

 

1. X가 3으로 나누었을때 나누어 떨어지면 3으로 나눈다.

2. X가 2로 나누었을때 나누어 떨어지면 2로 나눈다.

3. 그냥 1을 뺀다.

 

예시로 확인해보자.

 

1의 경우는 연산작업이 필요가 없기에 연산 수는 0

2의 경우는 2로 나누어떨어지기에 연산 횟수는 1

3의 경우는 3으로 나누어 떨어지기에 연산회수는 1

10의 경우에는 (10 - 1) / 3 / 3의 연산을 해야하기에 연산 횟수는 3

 

이를 따라, 점화식을 구해보자면

 

2의 경우는 

dp[i] = dp[i/2] + 1; 

3의 경우는

dp[i] = dp[i/3] + 1;

10의 경우는 

dp[i] = dp[i-1] + 1과 dp[i] = dp[i/3] + 1;을 함께사용하였다.

 

즉

dp[i] = dp[i/2] + 1; 

dp[i] = dp[i/3] + 1;

dp[i] = dp[i-1] + 1;

 

세가지의 점화식을 구할 수 있다.

 

여기서 끝에 + 1을 더해주는 것은 결국 2또는 3으로 나누었을때 연산과 - 1 을 해주었을때 연산 카운트라고 보면 된다.

 

아래 코드를 확인해보자.

 

Code ( C++ )

#include <iostream>
#define MAX 1000001
using namespace std;

int N;
int dp[MAX];

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

	cin >> N;

	for (int i = 2; i <= N; i++)
	{
		dp[i] = dp[i - 1] + 1;

		if (i % 2 == 0)
		{
			if (dp[i] >= dp[i / 2] + 1)
				dp[i] = dp[i / 2] + 1;
		}
		if (i % 3 == 0)
		{
			if (dp[i] >= dp[i / 3] + 1)
				dp[i] = dp[i / 3] + 1;
		}
	}

	cout << dp[N];
}