[백준 1463] 1로 만들기

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

Top-Down으로 푸니깐 메모리 초과가 난다. 파이썬으로 알고리즘 풀면 뭔가 코드가 간결하긴 한데 이런거에 있어서 제약이 심한듯 ㅠ

재귀함수 사용할 때 recursion제한도 풀어주어야 하고... 고려할게 많다.

 

bottom-up으로 풀면 쉽게 풀린다.

 

x = int(input())

dp = [987654321 for _ in range(1000000+1)]

dp[1] = 0

for i in range(2, x+1):
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    dp[i] = min(dp[i], dp[i-1] + 1)

print(dp[x])

 

 

c++

 

 

#include<iostream>
int dp[1000001];
using namespace std;
int min(int a,int b){
	return a<b?a:b;
}
int findAnswer(int N){

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

int main(){

	int N;
	cin>>N;
	cout<<findAnswer(N);

	return 0;
}