[python 백준] 1463번 1로 만들기

문제 링크

1463번: 1로 만들기

문제 설명

• 입력으로 받는 수 x에 대해 세 가지 종류의 연산을 반복해 1로 만들 수 있는 방법 중 연산 횟수가 가장 작은 방법의 연산 수를 찾는 문제
• 연산의 종류는 다음과 같다.
  1. x가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. x가 2로 나누어 떨어지면, 2로 나눈다.
  3. 모두 해당 없으면 1을 뺀다.

고민한 부분

• 단순하게 생각해 숫자를 가장 빠르게 줄일 수 있는 연산 순서로 조건을 확인하도록 구현했다가 틀렸다.
• 연산 횟수의 수열이 증가하는 수열이 아니기 때문에 어떤 연산을 적용하는 것이 가장 좋은지 알 수 없다.
• 1부터 x까지 거꾸로 거슬러 올라가며 그 사이에 있는 값들 각각의 최소 연산수를 계산하는 방식으로 x의 최소 연산수를 구할 수 있을 것이라고 생각했다.
  • x에 연산을 수행해 1로 만드는 모든 경우의 수를 확인하기 위해선 3번 연산만으로 1로 만드는 경우부터 시작해 1번과 2번 연산의 횟수를 증가시키며 시뮬레이션을 수행해야한다. 이와 같은 방법으로 해결하는 것은 적절하지 않다.
• x의 연산 최소 횟수를 $DP[x]$라고 하자.
• x가 3의 배수이면서 2의 배수라면 $DP[x]$는 $DP[x/3]$, $DP[x/2]$과 $DP[x-1]$ 중 최소값에 1을 더한 값이다.
  • 예를 들어, x가 12라면 3으로도 나누어지고, 2로도 나누어진다. $DP[12]$는 $DP[4]$, $DP[6]$, $DP[11]$ 중 최소값에 1을 더한 값이다.
• dynamic programming 방식으로 풀기 위한 $DP$의 점화식은 엄밀하지 않은 방식으로 다음과 같이 정의할 수 있다. 아래 식에서 $DP$의 index가 정수인 경우만 고려하면 된다.
  $$DP[x]=min(DP[x/3],DP[x/2],DP[x-1])+1$$
• 이를 코드로 구현만 해주면 되기 때문에 구현 자체는 어렵지 않다.

	x = int$input($)
	DP = [0]*$x + 1$ #DP 1은 0
	for idx in range$2, x+1$:
	if idx % 6 == 0:
	DP[idx] = min$DP[idx-1],DP[idx//3], DP[idx//2]$ + 1
	elif idx % 3 == 0:
	DP[idx] = min$DP[idx-1],DP[idx//3]$ + 1
	elif idx % 2 == 0:
	DP[idx] = min$DP[idx-1],DP[idx//2]$ + 1
	else:
	DP[idx] = DP[idx - 1] + 1
	print$DP[-1]$

view raw boj_1463.py hosted with ❤ by GitHub

Lesson learned

• DP 개념을 공부했지만 문제를 보고 Dynamic programming으로 풀이할 생각은 하지 못했다. 힌트를 보고 풀이를 떠올렸는데 몇 문제 더 풀어보면 좋을 것 같다.