1463 1로 만들기

1로 만들기 (1463)

 

풀이코드 (Top-down 재귀)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1463 1로 만들기
int INF = 123456789;
int n;
// idx 의 수를 1로 만들 수 있는 연산의 최솟값을 저장한다.
int cache[1000001];

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

int makeOne(int current){
	// 기저 사례 : 1이 되면 return 
	if(current == 1) return 0;
	
	int& ret = cache[current];
	// 기저 사례 : cache 에 값이 있으면 return
	if(ret != -1) return ret;
	
	int div3, div2, minus1;
	
	div3 = current % 3 == 0 ? makeOne(current / 3) : INF;	
	div2 = current % 2 == 0 ? makeOne(current / 2) : INF;	
	minus1 = makeOne(current - 1);	
	
	ret = min(min(div3, div2), minus1) + 1;
	
	return ret;
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	
	fill_n(cache, n + 1, -1);
	
	cout << makeOne(n) << '\n';
	
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 제한시간이 0.15초 이므로 일반적인 재귀로는 불가능 하다. 메모이제이션을 써볼까?

2. 작은 문제로 나누는 방법이 3가지. 일관성있는 답을 내놓는 문제들이다. 다이나믹 프로그래밍

3. 3 가지 경우를 모두 해본 뒤, min 값을 갖도록 하자. 도중에 메모이제이션을 쓰면서

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 처음 cache 배열을 설정할 때, 크기를 너무 작게 설정하여 런타임 에러가 발생하였다.

2. 그래서 엄청나게 크게 cache 의 크기를 설정하였더니 메모리 초과가 발생하였다.

3. 적당히 잡자