[Baekjoon] 1463번: 1로 만들기

🥅 문제

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

 

🔍 설계

시간 제한이 0.15초이고, N이 최대 1000000이므로, 보통 1초 당 1억 번의 연산을 하기 때문에 재귀함수를 사용한다면, Ω(N^2)의 시간 복잡도로 시간 제한을 초과한다. N에서 시작하는 것이 아니라, 반대로 1에서 시작하여 문제에서 주어진 연산을 반대로 하여 다이나믹 프로그래밍으로 설계한다면, O(N)으로 해결할 수 있다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, INF = 1e9+7;
vector<int> dp(1000001, INF);

int main() {
	cin >> n;
	dp[1] = 0;
	for (int i=1; i<n; i++){
		if (i*3 <= 1000000){
			dp[i*3] = min(dp[i*3], dp[i]+1);
		}
		if (i*2 <= 1000000){
			dp[i*2] = min(dp[i*2], dp[i]+1);
		}
		if (i+1 <= 1000000){
			dp[i+1] = min(dp[i+1], dp[i]+1);
		}
	}
	cout << dp[n] << "\n";
	return 0;
}

dp[i]는 i로부터 1을 만들기 위해 필요한 연산의 최소 횟수를 저장한다. 연산의 최소 횟수를 계산할 때, 인덱스가 배열의 범위를 초과할 수 있으므로, 조건을 달아주어야 한다.

 

📝 메모

반대로도 생각해보는 습관 기르기