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

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

1463번: 1로 만들기

 

1. 내가 작성한 코드

import sys

num = int(sys.stdin.readline().rstrip())

dp = [0,0,1,1]

dp = dp + [0] * (num-3)

if num >= 4:
  for n in range(4,num+1):

    if n % 2 == 0 and n % 3 == 0: #2,3 모두 나누어 떨어지는 경우
      dp[n] = 1 + min(dp[n//2],dp[n//3],dp[n-1])

    elif n % 2 == 0: #2로만 나누어 떨어지는 경우
      dp[n] = 1 + min(dp[n//2],dp[n-1])

    elif n % 3 == 0: #3으로만 나누어 떨어지는 경우
      dp[n] = 1 + min(dp[n//3],dp[n-1])

    else: #2,3모두 나누어 떨어지지 않는 경우
      dp[n] = 1 + dp[n-1]

print(dp[num])

 

n을 1로 만들 때까지 걸리는 횟수의 최솟값을 출력해주면 되는 문제이다.

 

이 문제의 포인트는 2나 3으로 나누어 떨어질 때 무작정 나누기를 진행하면 최적의 값을 찾을 수 없다는 것이다.

 

ex) n = 10

 

5(10 % 2) => 4(5 - 1) => 2(4 % 2) => 1(2 % 2) (4회) 최적 x

9(10-1) => 3(9%3) => 1(3%3) (3회) 최적 o

 

2. 문제 해결 및 수정 코드

 

1을 뺀 경우, 2로 나눈 경우, 3으로 나눈 경우의 min 값을 구하면 된다.

 

나는 아래와 같이 4가지의 경우를 나눠서 조건문을 만들었고, 꽤나 비효율적이라는 걸 느꼈지만,, 그냥 풀었다,,

 

1) 2,3 모두 나누어 떨어지지 않는 경우

2) 2로만 나누어 떨이지는 경우

3) 3으로만 나누어 떨어지는 경으

4) 2,3 모두 나누어 떨어지는 경우

 

num = int(input())

dp = [0,0,1,1]

dp = dp + [0] * (num-3)

if num >= 4:
  for n in range(4,num+1):

    dp[n] = 1 + dp[n-1]

    if n % 2 == 0:
      dp[n] = min(dp[n//2]+1,dp[n])
    
    if n % 3 == 0:
      dp[n] = min(dp[n//3]+1,dp[n])

print(dp[num])

 

위 코드처럼 단순하게 구현할 수 있다.