[백준] 1463번 1로 만들기 (DP)

해당 문제 링크입니다.

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

1463번: 1로 만들기

 

1. 처음생각

- DFS로 풀면 되겠다!

#include<iostream>
#include<vector>

using namespace std;
int answer;
void Solution(int n, int c) {
	if (n == 1) {
		if (answer > c)answer = c;
	}
	else {
		if (n % 3 == 0)
			Solution(n / 3, c + 1);
		if (n % 2 == 0)
			Solution(n / 2, c + 1);
		Solution(n - 1, c + 1);
	}
}
int main() {
	int N;
	answer = 987654321;
	cin >> N;
	Solution(N, 0);
	cout << answer << "\n";

	return 0;
}

---

- 하지만 실패했다.. 시간초과 났음.

- 1000만 넘어가도 일일이 다 탐색하는 것은 시간이 너무 오래걸린다. 재귀라서!! 

- 그렇다면 DP로 풀어야겠구만

 

2. 두번째 생각

- DP를 공부했음.. 핵심은 table 만들기!!

- 손으로 한번 돌려보는거 중요하다고 생각한다. 일단 이전 값보다 하나 증가한거 기본으로 놓고, 3으로 나눈거, 2로 나눈거랑 비교해주면 된다.

#include<iostream>
#include<vector>

using namespace std;

int Solution(int n) {
	vector<int> dp(n+1,0);
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)dp[i] = dp[i / 3] + 1;
		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)dp[i] = dp[i / 2] + 1;
	}
	return dp[n];
}
int main() {
	int N;
	cin >> N;
	cout << Solution(N);

	return 0;
}

잘 통과되었다.