[BOJ_1463] 1로 만들기

10을 세 가지 연산을 이용하여 1로 만든다고 할 때 모든 경우 중에 가장 작은 수를 찾아내야 합니다.

10 -> 9 -> 8 -> 7 -> ... -> 1 (x)

10 -> 9 -> 3 -> 1 (o)

* 점화식: 수열의 각각의 항들의 관계를 나타낸 식

모든 경우의 수를 고려할 경우 점화식을 떠올리는 방법을 생각해 내는 것이 좋은 방법이 될 수 있습니다.

이 문제의 경우 수를 줄일 수 있는 연산은 세 가지 밖에 없으므로 점화식은 이 경우를 포함하여 적어줘야 합니다.

f(n) = 1 + min(f(n/3), f(n/2), f(n-1))

그런데 가령, f(n/3)이 반드시 존재하는 값은 아닐 수 있지만 이렇게 점화식 형태로 표현이 가능한 경우 다이나믹 프로그래밍을 적용하여 문제를 해결하는 것이 가장 일반적이라고 합니다(사실 정확한 점화식을 발견하면 60%는 해결한 것이라고 생각합니다).

점화식에 1을 더해주는 이유는 함수의 호출 횟수를 구해줘야 하기 때문입니다. 연산을 한 번 더 할 때마다 1이 더해지기 때문에 몇 번을 연산했는지 트래킹 해 나갈 수 있습니다.

 

f(2) 부터 1을 만들기 위한 연산 횟수가 한 번이 발생하기 때문에

f(2) 부터 입력받은 x번째 항까지 dp 테이블을 채워나간다는 식으로 문제를 풀어보겠습니다.

x = int(input())
dp = [0 for _ in range(x+1)]
for i in range(2, x+1):
	dp[i] = dp[i-1] + 1
	if i % 3 == 0:
		dp[i] = min(dp[i//3] + 1, dp[i])
	if i % 2 == 0:
		dp[i] = min(dp[i//2] + 1, dp[i])
print(dp[x])

먼저 1을 뺀 경우로 dp 테이블을 1차 갱신 해 주고

2로 나누거나 3으로 나눈 방법이 더 효율적이기 때문에 파이썬의 min 함수로 나눌 수 있는 경우

재차 갱신을 해 줍니다.

www.acmicpc.net/problem/1463

1463번: 1로 만들기