[PS 백준 - 5.1] 1463번: 1로 만들기

문제 정보

백준 1463번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 다이나믹 프로그래밍

코멘트

다이나믹 프로그래밍(DP)을 접하면서 가장 처음 부딪히게 된 문제이다. 아직은 전혀 DP가 뭔지 감이 안 잡혀서 DP 블로그를 보면서 거의 똑같이 코드를 따라 써보았다.

DP에는 탑다운과 바텀업 방식 두가지가 존재한다. 나는 탑다운이 분할 정복 + 메모이제이션 개념을 다루는데 더 편리한 것 같아서 우선 탑다운 방식으로 DP 문제들을 푸는데 익숙해지려고 한다. 바텀업 방식의 코드는 임시로 동기(zzoni)의 코드를 가져와서 작성할 예정이다. (이 친구가 나보다 코드를 간결하게 잘 써서 공부하기에 좋다. 배울 점이 많은 친구다.)

• [Parameters]
  • n: 현재 숫자
• [base case]
  • n이 1일 때 0 리턴
• [Logic]
  1. n이 3의 배수일 때 3으로 나눈 후 재귀호출한 뒤, 결과값에 1을 더한 값을 벡터에 대입한다.
  2. 2의 배수일 때는 2로 나눈 값으로 재귀호출한 뒤, 결과값에 1을 더한 값을 벡터에 대입한다.
  3. 1을 뺀 값으로 재귀호출한 뒤, 결과값에 1을 더한 값을 벡터에 대입한다.
  4. 벡터 값들 중에서 가장 작은 값을 메모이제이션 + 리턴한다.

소스 코드

<탑다운 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int dp[1000001]{ 0, };

int func(int n) {
	vector<int> vec;
        // base case
	if (n == 1) { 
		return 0;
	}
    
        // memoization
	if (dp[n] > 0) { return dp[n]; } 
    
	if (n % 3 == 0) {
		vec.push_back(func(n / 3) + 1);
	}
	if (n % 2 == 0) {
		vec.push_back(func(n / 2) + 1);
	}
	vec.push_back(func(n - 1) + 1);
	
	int min = vec[0];
	for (int i = 0; i < vec.size(); i++) {
		if (min > vec[i]) min = vec[i];
	}
	dp[n] = min;
	return min;
	
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int x;
	cin >> x;
	cout << func(x);
}