1로 만들기 #1463 c++ 풀이

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

먼저 그냥 재귀가 떠올라서 막 코딩했을때, 시간초과가 났다.

dp라는 것을 제대로 이해하지 못한것이었다.

#include<iostream>

using namespace std;
/*
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
*/

int dp(int x, int cnt) {
	int count = cnt;
	int a=987654321, b=987654321, c=987654321;
	if (x == 1)
		return count;
	if (x % 3 == 0) {
		a= dp(x / 3, count+1); 
	}
	if (x % 2 == 0) {
		
		b = dp(x / 2, count+1); 

	}
	c= dp(x - 1, count+1);
	int mini = c;
	int temp = min(a, b);
	mini = min(c, temp);
	return mini;
}
int main() {
	int x;
	cin >> x;
	int cnt = 0;
	cout << dp(x, cnt);

}

생각해보면, 메모이제이션이 되고있지도 않는데, 

우선 이 코드를 메모이제이션 기법을 활용해봐야겠다는 생각을 했다.

 

int dp[1000001];

메모이제이션을 활용하려면 먼저 자료구조가 필요할 것이다.

 

내가 만든 코드를 dp로 이용하기위해서는,

dp[n]번째 값을 넣고, 그 값이 있다면 더이상 계산하지 않고 해당 값을 꺼내오는 방식을 사용해야할 것이다. 

 

#include<iostream>
#include<algorithm>

using namespace std;

int dp[1000001]; // 최대 입력 범위에 따라 배열 크기를 조절하세요.

int solve(int x) {
    dp[1] = 0; // 1을 1로 만드는데 필요한 연산 횟수는 0입니다.
    
    for (int i = 2; i <= x; i++) {
        dp[i] = dp[i - 1] + 1; // 1을 뺀 경우
        
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1); // 2로 나눈 경우
        }
        
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1); // 3으로 나눈 경우
        }
    }
    
    return dp[x];
}

int main() {
    int x;
    cin >> x;
    cout << solve(x);
    return 0;
}