백준 1463 번 : 1로 만들기

문제 접근

---

count 가 최소가 되도록 DP 로 구현했다. return  할 때, 1 + ( 세 가지 연산의 각 경우 중 최솟값 ) 을 반환하기에 cache[n] 에는 숫자 n 이 1 로 되는 최소 연산 횟수가 저장되어있고, 이를 통해 중복을 빠르게 처리하여 답을 구할 수 있다.

 

 

문제 코드

---

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int cache[1000001];

int count(int n)
{
	int& ret = cache[n];
	
	if(ret != -1)
		return ret;
	if(n == 1)
		return ret=0;
	
	int d3,d2,m1;
	d3=d2=m1=1000001;
	
	if(n % 3 == 0 && n > 2)
		d3 = count(n/3);
	
	if(n % 2 == 0 && n > 1)
		d2 = count(n/2);
	
	m1 = count(n-1);
	
	return ret = 1 + min(m1,min(d2,d3));
}

int main(void)
{
	int x;
	memset(cache, -1, sizeof(cache));
	scanf("%d",&x);
	printf("%d\n",count(x));
	return 0;
}