백준 1463 풀이

링크텍스트

처음 문제를 보았을 때는 그냥 단순하게 연산 1,2,3을 if문을 활용하여 입력받은 수가 1이 될 때까지 반복하는 방식으로 풀이를 했다.

당연히 틀렸다.

	while (x != 1) {
		if (x % 3 == 1) {
			x = x - 1;
			answer++;
			continue;
		}
		if (x % 3 == 2) {
			x = x - 1;
			answer++;
			continue;
		}
		//1번 연산 검사
		if (x % 3 == 0) {
			x = x / 3;
			answer++;
			continue;
		}
		if (x % 2 == 0) {
			x = x / 2;
			answer++;
			continue;
		}
		if (x % 3 != 0 && x % 2 != 0) {
			x = x - 1;
			answer++;
			continue;
		}
    }

무언가 익숙한 방식으로 틀리는데...

저번에도 이런 문제를 비슷한 방식으로 풀다가 답은 답대로 안나오고 코드는 코드대로 지저분해져서 다 지우고 다시 푼 적이 있었다.
그런 경험을 바탕으로 이번에는 빠르게 다시 생각을 했다.
입력받은 수를 1부터 차근차근 증가시키며 규칙을 찾으려고 했고 20까지 적었을 때 규칙을 찾았다.

일단 풀이 방식은 다이나믹 프로그래밍을 써야한다는걸 알았다.
그리고 2의 배수 혹은 3의 배수가 아닌 경우 지금 인덱스의 값은 이전 인덱스의 값에 1을 더한 것과 같다는 규칙을 찾았다.(dp[i] = dp[i-1]+1)

이제 2의 배수일 때 혹은 3의 배수일 때인데 3으로 나누어 떨어진다는 것은 결국 이전의 3의 배수에서 연산을 한번 더 한 것과 마찬가지이므로 dp[i] = dp[i/3]+1과 같다. 2의 배수 또한 마찬가지이다.

이렇게 생각을 하고 코드를 제출했으나 또 틀렸다...

반례가 있나 싶어 게시판을 돌아다니다 알게되었다. 단순히 dp[i/3]+1 한 값이 dp[i-1]+1보다 클 수 가 있다는 것을 말이다.

이를 토대로 코드를 다시 수정한 결과 정답을 찾을 수 있었다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int dp[1000001];

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

	int answer = 0;
	int x;
	cin >> x;

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	dp[6] = 2;

	for (int i = 7; i <= x; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0) {
			dp[i] = min(dp[i / 3]+1, dp[i]);
		}
		if (i % 2 == 0) {
			dp[i] = min(dp[i / 2]+1, dp[i]);
		}
	}
	cout << dp[x] << '\n';
	return 0;
}