[Python] BOJ(백준) 1463번 - 1로 만들기

1. 링크

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

2. 난이도(solved.ac 참고)

실버3

3. 풀이

	# https://www.acmicpc.net/problem/1463
	import sys
	f = sys.stdin.readline
	n = int(f())
	dp = [0] * 100001
	for i in range(2, n+1):
	dp[i] = dp[i-1] + 1
	if i % 3 == 0:
	dp[i] = min(dp[i], dp[i//3]+1)
	if i % 2 == 0:
	dp[i] = min(dp[i], dp[i//2]+1)
	print(dp[n])

view raw 1로만들기.py hosted with ❤ by GitHub

재귀형태의 다이나믹 프로그래밍으로 해결하였는데, 이렇게 푼 사람들이 많은 걸 보면 그냥 이렇게 풀라고 낸 문제 같다.

여기에서 dp배열의 값들은 1로 만드는 데 걸리는 횟수들이다.

여기에서 우선 dp[i] = dp[i-1] + 1은 그냥 1을 빼줬을 때에 해당한다. 그냥 빼기만 하면 이전 횟수에 비해 1회가 추가되는 것이 끝이기 때문.

2와 3으로 나눠질 경우, 횟수가 1회 추가되었으므로 dp[i//3]이나 dp[i//2]의 값에 +1을 해줬다. 그리고 그 값을 기존에 있던 dp[i-1]+1의 값과 비교를 해주었다.