[백준] 1463번 1로 만들기

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

 

---

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> 이유는 메모이제이션을 하지 않는다면, Top-down 방식 (재귀함수)로 풀었을 때 n / 3, n / 2, n - 1로 3 경우의 모든 경우를 다해본다면 N이 10^6 일 때 (3^10)^6의 시간이 걸릴 수가 있다.

​

(2) 다이나믹 프로그래밍을 처음 접하신 분들이라면 이 문제를 통해서 메모이제이션의 필요성, 동작 방식을 정확히 이해했으면 한다.

​

(3) 아래 그림은 n이 10일 때 함수 동작 방식에 대한 설명이다.

 

-> 위 그래프에서 10부터 1까지의 간선의 개수가 연산 횟수와 같다.

2. Source Code

 

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 1000001
#define INF 987654321
using namespace std;
// dp[i]는 숫자 i일 때 최소 연산 횟수
int dp[MAX];

// 10을 예로 들어보자
// 10 -> 5 -> 4 -> 2 -> 1
// 10 -> 9 -> 3 -> 1
int solution(int n)
{
	// 기저사례
	if (n == 1) return 0;

	int& result = dp[n];
	if (result != -1)
		return result;

	result = 0;
	int c1, c2, c3;
	c1 = c2 = c3 = INF;
	if (n % 3 == 0)
	{
		// solution() + 1의 의미는 현재까지 연산횟수이다.
		c1 = solution(n / 3) + 1;
	}
	if (n % 2 == 0)
	{
		c2 = solution(n / 2) + 1;
	}
	c3 = solution(n - 1) + 1;
	return result = min(min(c1, c2), c3);
}


int main()
{
	int n; cin >> n;
	memset(dp, -1, sizeof(dp));
	cout << solution(n);
	return 0;
}