[백쥰 1463] 1로 만들기 (DP) - Python

✏️문제

 

✏️풀이

전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다. 즉, 메모제이션 방법으로 중복해 계산되는 값을 저장해 계산의 효율을 높일 수 있다.

 

DP로 푸는건 알겠는데, 주어진 N -> 1 로 접근했더니 머리가 아팠다...

결국 풀지 못하고 풀이를 참고했고, 상향식(bottom-up) 으로 푸는 것을 알게되었다.

 

• X = 10인 경우, 10 -> 9 -> 3 -> 1  과정을 거쳐 1이 되게 되는데
• 9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며
• 3의 경우에는 3 -> 1의 과정을 거친다.

=> 즉, 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.

앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다!

 

일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에, 조건에 걸리지 않는 상단에 

dp[i] = dp[i-1] + 1을 통해 횟수를 +1 해주었다.

 

이후후, dp[i]가 2 와 3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i//2or3]+1(나누었을 경우) 중 최소값을 선택한다.

 

그래도, dp가 무엇인지 다시 한 번 감을 잡게되었다.

나중엔 스스로 풀어봐야겠다

✏️코드

N = int(input())

# DP 테이블 초기화
dp = [0] * (N+1)
# 다이나믹 프로그래밍 진행(bottom-up)
for i in range(2, N+1): # i=2,3,4,5,6,7,8,9,10
    # 현재의 수에서 1을 빼는 경우
    dp[i] = dp[i-1] + 1 #dp[2] = dp[1] + 1 = 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    print("dp:",dp)


# 결과 출력
print(dp[N])

 

✏️참고

https://velog.io/@qtly_u/DP-%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

DP, 백준 1463번(Python) -1로 만들기