BOJ3910 거듭제곱 계산(C++)

---

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

태그 : 그래프 탐색, DFS(IDDFS?)

---

풀이

처음엔 DFS나 BFS로 접근하려 했는데,

꽤 고민을 해봐도 방법이 떠오르지 않았다.

백트래킹 태그를 봐도 감이 잘 오지 않았다.

그래서 Gemini의 도움을 받았다.

---

IDDFS

이름부터 거창하다. Iterative Deepening DFS, 반복적 깊이 심화 탐색

DFS를 하는데, BFS에서 탐색마다 깊이를 하나씩 늘리는 것처럼

깊이 상한을 늘려가며 DFS 범위를 늘려가는 것이다.

태그에 전처리가 있어서 그냥 1부터 1000까지 최소거리를 다 넣는걸 생각했지만,

이 방식대로라면 그냥 매 입력마다 dfs를 하는것이 정답인 것 같다.

---

구현

limit을 1부터 늘려가며 반복한다.

1부터 dfs를 시작하고,

limit 1 : 1 -> 종료
limit 2 : 1 -> 2 종료
limit 3부터 조금씩 갈린다.
limit 3 : 1 -> 2 이후 2 + 2로 4로도 갈 수 있고, 1 + 2로 3으로도 갈 수 있다.

이런 식으로 모든 조합을 테스트 해보는 것이다.

limit을 제한이 없이 dfs 한다면 도착은 보장할지 몰라도 최소 횟수는 보장이 안된다.

이 단점을 bfs의 레벨 단위 탐색 개념을 넣어 보완한 것이라고 보면 되겠다.

---

코드

#include <iostream>
using namespace std;

int n;
int arr[2001];
int ans;

bool iddfs(int cur, int depth, int limit) {
	if (cur == n) {
		return true;
	}

	if (depth == limit) {
		return false;
	}

	if (cur << (limit - depth) < n) {
		return false;
	}

	arr[depth] = cur;

	for (int i = depth; i >= 0; --i) {

		int nextSum = cur + arr[i];
		if (nextSum < 2001) {
			if (iddfs(nextSum, depth + 1, limit)) {
				return true;
			}
		}
	}
	
	for (int i = 0; i <= depth; ++i) {
		int nextSub = cur - arr[i];
		if (nextSub > 0) {
			if (iddfs(nextSub, depth + 1, limit)) {
				return true;
			}
		}
	}

	return false;
}

void solve() {
	int limit = 1;
	while (true) {
		
		if (iddfs(1, 0, limit)) {
			ans = limit;
			break;
		}


		++limit;
	}
	
}

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

	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		if (n != 1) {
			solve();
		}
		else {
			ans = 0;
		}
		cout << ans << '\n';
	}

}

---

후기

AI 없었다면 IDDFS라는 태그도 모른채 남겨놨을 문제이다.

레퍼런스도 없었다... 아마 코테에서 볼 일은 없지 않을까 ?