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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1463번 1로 만들기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정수 N을 다음 연산으로 1로 만들 때, 필요한 최소 연산 횟수를 구하는 문제입니다.

• X가 3으로 나누어떨어지면 X / 3
• X가 2로 나누어떨어지면 X / 2

• X - 1

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

n = int(input())

cnt = [100000 for _ in range(n+1)]
cnt[1] = 0

for i in range(1, n):
    if i*3 <= n:
        cnt[i*3] = min(cnt[i*3], cnt[i]+1)
    if i*2 <= n:
        cnt[i*2] = min(cnt[i*2], cnt[i]+1)
    cnt[i+1] = min(cnt[i+1], cnt[i]+1)
    
print(cnt[n])

설명

cnt[x]를 “1에서 시작해서 x에 도달하는 최소 연산 횟수”로 두고 테이블을 채우는 DP입니다.

• cnt[1] = 0에서 시작
• 각 i에서 i*2, i*3, i+1로 갈 수 있으면 +1 비용으로 갱신
• 최종적으로 cnt[N]이 답

연산을 역으로 생각하면( N에서 1로 ),
정방향으로는 작은 수에서 큰 수를 갱신해 나가는 방식으로 같은 최소값을 얻을 수 있습니다.

---

• 백준 문제풀이 전체 목록 보기

---