[BaekJoon] 백준 1463번 : 1로 만들기

1463번 : 1로 만들기

위 세 가지 연산을 가지고 최소한의 연산을 통해 1을 만들면 되는 문제.

무언가 어떤 과정을 거쳐 목표로 가는데 있어서 작업의 수의 최솟값이나 최댓값을 구할 땐 DP 를 사용하면 된다.

또는 피보나치 수를 구하는 것 처럼 어떤 목표에 도달 할 때 중복 작업을 굉장히 많이 하면 DP 를 사용하면 될 것 같다.

이 문제는 Bottom - Top DP 를 사용하면 된다. 우리는 N 이 1, 2, 3 일땐 각각 0, 1, 1 이란 것 을 알고 있다.

따라서 사전에 1, 2, 3 일때 최소 연산 횟수를 저장 해 준 뒤 N 이 4 일때 부터 계산을 하면 된다.

만약 N 이 6 이 입력된다면 6 % 3 , 6 % 2, 6 - 1 을 키로 하는 값을 찾아 그 중 최솟값과 1 을 더해주면 된다.

이 경우 num_dict[2] , num_dict[3] , num_dict[5] 중에 최솟값인 1 을 더해주면 된다.

위에선 DP 를 사용하면 된다고 했는데 DP 를 사용 해야겠다는 생각을 하기가 아직 어려운 것 같다..

---

N = int(input())
answer = 0
num_dict = {
	1: 0,
	2: 1,
	3: 1
}

for i in range(4, N + 1):
	check = []
	if i % 3 == 0:
		check.append(num_dict[i // 3])

	if i % 2 == 0:
		check.append(num_dict[i // 2])

	check.append(num_dict[i - 1])

	num_dict[i] = 1 + min(check)

print(num_dict[N])