[백준] 1463번 1로 만들기 파이썬

이코테 책의 그리디 파트에서 1이 될 때까지 문제를 풀고 난 이후에 이 문제를 발견해서 비슷하겠지 싶어서 도전해 보았다.

 

1463번 1로 만들기 풀이

 

[고민] 

n = int(input())
cnt = 0

while n != 1:
  if n % 3 == 0:
    n = n / 3
    cnt += 1
  else:
    if n % 2 == 0:
      n = n / 2
      cnt += 1
    else:
      n = n - 1
      cnt += 1

print(cnt)

1이 될 때까지 문제를 풀었을 때는 2가지 경우여서 간단하게 풀 수 있었지만 이 문제는 단순히 횟수만 구해서는 안된다. 처음에는 너무 간단하네~ 하고 예제 입력 10을 넣었더니 3이 나와야하는데 4가 출력되었다. 10 -> 9 -> 3 -> 1로 3번 만에 가능하기 때문이다. 즉, 3으로 나누기, 2로 나누기, 1로 빼기 중에서 어떤 방법이 가장 작은 값을 만들 수 있을지 찾아야 하는데 어떻게 기록을 해두고 최소를 찾을지가 관건이었다.

 

잘 모르겠어서 구글링하여 다른 언어로 문제를 해결하신 분들의 풀이를 보니까 DP문제라고 했다. Dynamic Programming은 이전의 결과를 다음 연산에 이용하는, 점화식을 활용하는 유형을 말한다. 그리고 기존 연산된 값을 재사용하는 것을 메모이제이션이라고 표현하더구먼요. 호호.

 

최솟값을 구할 때에 그리디 알고리즘과 동적 계획법을 많이 사용하는 듯한데 그리디는 최적의 방법으로 처음부터 끝까지 반례 없이 적용된다면 사용하고, 동적 계획법은 모든 가능성들 중에서 최솟값을 찾는 것이라고 한다.

 

점화식 : DP(N) = min(DP(N−1), DP(N/2), DP(n/3))

 

#솔루션

n = int(input())
dp = [0] * (n + 1) #또는 dp = [0 for _ in range(n+1)] 

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])

여러 풀이를 보고, 이렇게 풀면 좋았겠다 싶은 코드로 적어 보았습니다.

 

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

1463번: 1로 만들기