백준 1463 [C++] - 메모리초과

www.acmicpc.net/problem/1463

1463번: 1로 만들기

1. 풀이방법

 

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

 

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

 

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

 

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

 

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

 

 

 

 

2. 주의사항

 

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

 

-결과는 "메모리 초과"

 

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

 

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

 

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

 

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

 

 

 

 

3. 나의코드

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

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}