[백준 알고리즘] 1463번 1로 만들기, 파이썬(python)

1463, 1로 만들기

📁 문제 출처

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

 

💡 생각

• n을 3으로 나누기 -> 안 나눠지면 -1 해주고 3으로 나누기 -> 이것도 안되면 2로 나눠주기 -> 안되면 -1 진행

 

오답

n = int(input())

count = 0
while n != 1:
    if n % 3 == 0:
        n //= 3
        count += 1
    elif (n-1) % 3 == 0:
        n //= 3
        count += 2
    elif n % 2 == 0:
        n //= 2
        count += 1
    else:
        n -= 1
        count += 1

print(count)

• 위와 같은 아이디어를 세웠지만 틀렸다.
• 이 문제는 DP로 접근해야 한다.
• bottom-up방식과 dp에는 연산 횟수를 저장해줘야 하는 힌트를 얻음

 

🛠 나의 코드

n = int(input())

dp = [0] * (n + 1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # 1을 빼주는 것 부터 처리, +1을 해주는 것은 연산횟수를 더해주는 것. 즉, 마이너스 연산만 수행한거니까 [i-1]의 연산횟수에 +1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1) # i가 2로 나눠지면 이전에 i//2의 연산횟수에 +1, 그리고 둘 중 연산횟수가 낮은 것을 dp[i]에 저장
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1) # i가 3로 나눠지면 이전에 i//3의 연산횟수에 +1, 그리고 둘 중 연산횟수가 낮은 것을 dp[i]에 저장

print(dp[n])

 

✔️ 배운 점 및 주의할 점

• 처음에는 count 변수를 만들어서 연산 횟수를 더해주려고 했었다. 그러나 생각해보면 연산 횟수를 구하는 문제이기에 dp에 연산 횟수를 저장하는 것이 당연한? 건데 그 부분까지 생각하지 못했다.
• DP는 규칙을 찾고 점화식을 세우는 것이 제일 중요하다.
• bottom-up으로 구현하는 것을 권장