BOJ1463 1로 만들기

아이디어

---

이 문제는 예전에 C#으로 풀어본 적이 있는데 어떻게 풀어본지 기억이 안났다. 문제 분류를 안보고 푸는 습관을 최근 들이고 있어서 처음엔 조건문을 여러 개 거치는 그리디 방식으로 접근했다. 나름 빈틈 없이 조건문을 작성했다고 생각했는데도 계속 예외가 나오니 그리디는 아니겠지 싶었다. 그래서 종이에 숫자를 쭉 써놓고 최소 연산 횟수를 적다가 문득 DP배열을 사용해서 풀면 되겠다는 생각이 들었다.

1. 1, 2, 3은 각각 0, 1, 1으로 저장하고 시작
2. 4 이상의 값 n부터는 n-1, n/2, n/3의 연산 횟수를 확인하고 최소값에 1을 더한 값을 갖는다.
3. 입력받은 값까지 반복문을 돌려 해당 인덱스의 값을 불러온다.

제한시간이 0.15초로 굉장히 짧은 편이라 통과될지 긴가민가 했지만 무난하게 통과했다. O(n)이면 앵간히 케이스가 많은 경우가 아닌 이상 크게 신경쓰지 않아도 되지 않나 싶다.

해답

---

#include <bits/stdc++.h>
using namespace std;

int main() {
	int dp[1000000];
	int n;
	cin >> n;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 3; i < n; i++) {
		int cur = dp[i - 1];
		if ((i + 1) % 2 == 0)
			cur = min(cur, dp[(i + 1) / 2 - 1]);
		if ((i + 1) % 3 == 0)
			cur = min(cur, dp[(i + 1) / 3 - 1]);
		dp[i] = cur + 1;
	}

	printf("%d", dp[n - 1]);

	return 0;
}