[성실코딩 9일차] 백준 #1463 1로 만들기 / DP

질문 검색 글들 보면 N=140만까지도 입력으로 들어오는 것 같다.

아니면 배열을 140만이라고 할당하면 전부를 사용할 수 있는게 아닌건가?

200만 할당하면 문제 해결됨!

#include<iostream>
#include<algorithm>

using namespace std;

int DP[2000000] = { 0, }; // DP사이즈 : (10)<<6+1 -> 런타임 에러 

int main() {

	int n;
	cin >> n;

	//DP[0]=1
	for (int i = 1; i < n; i++) {
		int new_cnt = DP[i] + 1;
		// 3가지 작업
		// +1
		if (i + 1<=n) {
			if (DP[i + 1] != 0) {
				DP[i + 1] = min(DP[i + 1], new_cnt);
			}
			else {
				DP[i + 1] = new_cnt;
			}
		}
		
		// *2
		if (i * 2<=n) {
			if (DP[i * 2] != 0) {
				DP[i * 2] = min(DP[i * 2], new_cnt);
			}
			else {
				DP[i * 2] = new_cnt;
			}
		}
		
		// *3
		if (i * 3<=n) {
			if (DP[i * 3] != 0) {
				DP[i * 3] = min(DP[i * 3], new_cnt);
			}
			else {
				DP[i * 3] = new_cnt;
			}
		}
	}

	cout << DP[n] << endl;

	return 0;
}