백준 1463번: 1로 만들기

[문제 링크]

1463번: 1로 만들기

---

알고리즘 문제해결전략에서 배운 방식으로 메모이제이션하여 Top-down 방식으로 풀었는데 무난하게 정답처리를 받을 수 있었다.

하지만 필자가 사용하는 컴파일러인 Visual Studio 2017 환경에서 돌렸을 때 N이 8000정도만 넘어가도 스택 오버플로가 발생하였다.

원인은 N이 커지면 커질수록 재귀호출 횟수가 급격하게 증가하는데, 이때 프로그램이 컴파일러의 호출 스택에서 이용가능한 공간 이상을 사용하려다 충돌이 일어나게 되는 것이었다.

 

따라서 스택 오버플로 문제를 해결하기 위해 재귀호출이 아닌 for문으로 알고리즘을 구현하였고, 재귀호출 없이 Top-down 방식을 구현하는 것은 불가능하다 판단하여 Bottom-up 방식으로 문제를 해결하였다.

---

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int memo[1000001];

inline int min(int a, int b) { return a < b ? a : b; }

int TopDown(int N)
{
	if (N == 1) return 0;

	int& ret = memo[N];
	if (ret != -1) return ret;

	ret = 0;

	int A = INF, B = INF, C = INF;
	if (N % 3 == 0) A = 1 + TopDown(N / 3);
	if (N % 2 == 0) B = 1 + TopDown(N / 2);
	C = 1 + TopDown(N - 1);

	return ret = min(A, min(B, C));
}

int BottomUp(int N)
{
	memo[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		memo[i] = memo[i - 1] + 1;
		if (i % 3 == 0) memo[i] = min(memo[i], memo[i / 3] + 1);
		if (i % 2 == 0) memo[i] = min(memo[i], memo[i / 2] + 1);
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;
	
	memset(memo, -1, sizeof(memo));
	
	cout << BottomUp(N) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day