[알고리즘] 백준 1465번: 1로 만들기 (C++), DP의 점화식 접근이 꽤 어렵다

DP의 접근 방법이 꽤 어려웠다. 아무래도 점화식을 어떻게 세우는지 접근을 하지 못 했다. (BFS로 풀릴 거 같아서 BFS로 푼 풀이는 맨 아래에 첨부해두었다.)

 

그래서 다른 사람의 코드를 참고했다. (Bottom-Up 방식)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int cache[100001] = { 0, };

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

	cout << cache[n];
	return 0;
}

cache 배열에는 어떠한 값을 연산하기 위해 몇 번을 계산해야 하는지 최솟값이 들어간다.

 

3을 예시로 들어보면

먼저 맨 위의 체크된 부분에서 cache[3]이 2가 되어있다는 걸 알 수 있다.

체크된 부분은 어떤 n값에 계속 -1을 해주는 것이다.

하지만 if문에서 3이 3으로 나누어지기 때문에 cache[3]과 cache[3 / 3] + 1중 작은 값을 넣으라는 것을 볼 수 있다.

이 말의 뜻은 3에서부터 계속 -1을 해서 1로 만든 연산의 수가 더 적은 것이냐 혹은 3으로 나누고 (+1), (cache[3 / 3]은 이미 최솟값이 들어있다. => 앞선 반복문에서 이미 최솟값을 넣었다.) cache[1]까지의 연산이 더 큰가를 묻는다.

 

1을 계속 빼주는 것은 특정 조건이 없기 때문에 맨 위에 있어야 한다. 맨 위에 없을 경우 모든 cache의 값이 0인 상태에서 2로 나누었을 때 최소 연산 수와 0을 비교하기 때문에 당연히 0 밖에 넣지 못하기 때문이다.

 

---

느낀 점

아직도 점화식을 세우는 것에 큰 어려움을 느낀다. Bottom-Up과 Top-Down의 방식 차이는 어느 정도 문제들을 풀면서 감으로 익혔지만 (확실한 개념을 배워서 포스팅할 것) 점화식에 접근이 꽤 어렵다.

 

---

BFS로 풀었던 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

queue<pair<int, int>> q;
vector<int> answer;
bool visited[1000001] = { 0, };

void bfs(int n) {
	q.push(make_pair(n, 0));
	visited[n] = 1;

	while (!q.empty()) {
		int idx = q.front().first;
		int cnt = q.front().second;

		q.pop();
		
		if (idx == 1) {
			answer.push_back(cnt);
			continue;
		}

		if (idx % 2 == 0 && visited[idx / 2] == 0) {
			visited[idx / 2] = 1;
			q.push(make_pair(idx / 2, cnt + 1));
		}
		if (idx % 3 == 0 && visited[idx / 3] == 0) {
			visited[idx / 3] = 1;
			q.push(make_pair(idx / 3, cnt + 1));
		}
		if (visited[idx - 1] == 0) {
			visited[idx] = 1;
			q.push(make_pair(idx - 1, cnt + 1));
		}
	}
}

int main() {
	int n;
	cin >> n;
	bfs(n);
	sort(answer.begin(), answer.end());
	cout << answer.front();
	return 0;
}