[Baekjoon] 1463번: 1로 만들기

 

 

 

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

1463번: 1로 만들기

 

---

 

문제 해결 과정

착안

자연수 $n=1, 2, ..., N$ 에 대해 $n=1$ 부터 반복문을 통해 $n$의 값을 증가시키면서 $3n, 2n, n+1$ 에 대한 연산 횟수의 값을 동적계획법(dynamic programming)을 통해 최솟값으로 갱신함으로써 문제를 해결하고자 했다.

 

구현

주어지는 수 $N$ 보다 큰 수에 대해서는 계산할 필요가 없으므로, $n=i$ 일 때, $3i, 2i, i+1$ 의 값이 $N$ 보다 작거나 같을 때에만 계산을 하도록 하였다. $3i, 2i, i+1$ 의 연산 횟수가 이미 계산되어있는 경우에는 최솟값으로 갱신, 계산되어있지 않은 경우에는 $i$ 의 연산 횟수에 1을 더한 값으로 초기화하도록 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

char Counts[1000001];

int main()
{
	int N;
	cin >> N;

	int i = 0;
	while (i++ < N)
	{
		char cnt = Counts[i] + 1;

		if (3 * i <= N)
			Counts[3 * i] = Counts[3 * i] ? min(Counts[3 * i], cnt) : cnt;

		if (2 * i <= N)
			Counts[2 * i] = Counts[2 * i] ? min(Counts[2 * i], cnt) : cnt;

		Counts[i + 1] = Counts[i + 1] ? min(Counts[i + 1], cnt) : cnt;
	}

	cout << (int)Counts[N] << "\n";
	return 0;
}

 

그런데 이렇게 문제를 해결하고 나서 문제를 효율적으로 해결한 다른 분들의 코드를 살펴보니 정말 어이가 없을 정도로 간단히 해결하는 것을 확인하고 흥건하게 지렸다(아래 코드 참고).

 

고수들의 코드를 보고 그만 지려버렸다

 

최적화 된 코드를 이해하기 위해서는 문제에서 제시한 조건이 다음의 특징을 가진다는 것을 이해해야 한다.

 

• 주어지는 수를 최소 연산으로 1로 만들기 위해서는 3 또는 2로 나누는 연산을 최대한 많이 수행해야 한다.
• 주어지는 수를 1로 만드는 과정에서, 3 또는 2 중 어떤 수로 나누는 것이 더 유리한지는 계산해야만 알 수 있다.
• 주어진 숫자를 3 또는 2의 배수로 만들기 위한 연산 횟수는 각각 3, 또는 2로 나눈 나머지 연산으로 표현 가능하다.

 

[스포 주의] (최적화 코드) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

int Counts(int n)
{
	// n == 1 또는 n == 0 : 0을 반환
	// n >= 2 인 경우     : 1씩 줄여서 2의 배수로 만들어 2로 나누는 연산 횟수와
	//                      1씩 줄여서 3의 배수로 만들어 3으로 나누는 연산 횟수 중에
	//                      더 작은 수를 택하여 반환
	return n <= 1 ? 0 : 1 + min(Counts(n / 2) + n % 2, Counts(n / 3) + n % 3);
}

int main()
{
	int N;
	cin >> N;
	cout << Counts(N) << "\n";
	return 0;
}

 

실행 결과

위: 최적화 된 다른 분들이 짠 코드를 이용한 결과 / 아래: 동적계획법을 사용해 문제를 해결한 결과