[백준] 1463번 1로 만들기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 1463번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

1463번: 1로 만들기

문제 접근

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어집니다. 

 아래에 나와있는 세 가지 연산법만을 사용하여 최소횟수로 1로 만들고 그 최소 횟수를 출력하면 되는 문제입니다.

1. N이 3으로 나누어 떨어지면, 3으로 나눈다.

2. N이 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 빼준다.

 

 다이나믹프로그래밍 알고리즘으로 접근하였습니다.

 d[]리스트를 (n+1)개만큼 생성 후 d[n] 에 정수 n을 1로 만들기 위한 최소 연산 횟수를 담을 것 입니다. n은 1보다 크거나 같기 때문에 2부터 n까지 1로 만들기위한 최소 연산 횟수를 구하면 됩니다.

 우선 1, 2번은 각각 3과 2로 나누어 떨어지지 않으면 연산이 불가능하기 때문에 가장 먼저 3번 연산을 해주고 1, 2번 연산이 가능한지(3혹은 2로 나누어 떨어지는지)확인 후 가능하다면 1, 2, 3번 연산 중 최소 연산 횟수를 가지는 연산을 하고 그 횟수를 d리스트에 넣어줍니다.

 

 5까지의 연산을 예로 들어보겠습니다(n이 5일 경우). i는 2부터 5까지 반복하여 계산 합니다.

for i in range(2,n+1) :

    # 3번 연산 1을 뺀다.
    d[i] = d[i-1] + 1
    # 1번 연산 n이 3으로 나누어 떨어지면, 3으로 나눈다.
    if i % 3 == 0 :
        d[i] = min(d[i//3] + 1, d[i])
    # 2번 연산 n이 2로 나누어 떨어지면, 2로 나눈다.
    if i % 2 == 0 :
        d[i] = min(d[i//2]+1, d[i])

 

 i 값이 2일 경우입니다.

 가장 먼저 무조건 할 수 있는 연산인 3번 연산 처리를 해줍니다. d[2] = d[1]+1 -> d[2] = 1 ( 2를 1로 만들기 위해선 1을 빼주는 연산 한번 만 하면 된다는 뜻(+1)) {2-1}

 현재 i 값인 2는 2로 나누어 지지만 2에서 1을 빼주는 연산 횟수(1회){3번 연산} 2를 2로 나누어주는 연산 횟수(1회){2번 연산} 연산 횟수가 동일하기 때문에  d[2] = 1이 됩니다.

 

i 값이 3일 경우입니다.

마찬가지로 3번 연산 처리를 해줍니다. d[3] = d[2] +1 -> d[3] = 2 ( 3을 2로 만들고(+1) (1회) + 2에서 1로 만드는 최소 연산 횟수(d[2]) (1회)) {(3-1)-1}

그 후 i 는 3으로 나누어 떨어지기 때문에 1번 연산이 가능합니다. 1, 3번 연산을 비교하여 더 작은 연산 횟수를 찾습니다.

d[3] = min(d[3//3]+1, d[3]) -> d[3] = d[3//3] + 1 = 1 (d[3//3] = d[1] = 0)

3에서 1을 만드는 연산 횟수는 {(3-1)-1} (2회)가 아닌 {3//3} (1회) 이기 때문에 더 작은 연산 횟수로 d[3] = 1이 됩니다.

 

i 값이 4일 경우입니다.

 마찬가지로 3번 연산을 해줍니다. d[4] = d[3] + 1 -> d[4] = 2 (4를 3으로 만들고(+1) (1회) + 3에서 1을 만드는 최소 연산 횟수(d[3])  (1회))

그 후 i는 2로 나누어 떨어지기 때문에 2번 연산이 가능합니다. 2, 3번 연산을 비교하여 더 작은 연산 횟수를 찾습니다.

d[4] = min(d[4//2]+1, d[4]) -> d[4] = d[4//2]+1 = 2  (d[4//2] = d[2] = 1)

4에서 1을 만드는 연산 횟수는 {(4-1)//3} (2회), {(4//2)//2} (2회) 이기 때문에(동일) d[4] = 2가 됩니다.

 

 i 값이 5일 경우입니다.

가장 먼저 3번 연산을 해줍니다. d[5] = d[4] + 1 -> d[5] = 3 ( 5를 4로 만들고(+1) (1회) + 4에서 1을 만드는 최소 연산 횟수(d[4]) (2회)

5는 2나 3으로 나누어 떨어지지 않기 때문에 3번 연산만 가능하므로 d[5] = 3이 됩니다.

정답 코드

import sys

# 정수 n을 입력 받음
n = int(sys.stdin.readline().rstrip())

# n+1개만큼 리스트를 초기화
# ex) d[3]은 3을 1로 만드는데 드는 최소 연산 횟수가 담기게 됨.
d = [0] * (n + 1)

# 2부터 n까지 1을 만들기 위한 최소 연산 횟수를 구함.
for i in range(2,n+1) :

    # 3. 1을 뺀다.
    d[i] = d[i-1] + 1
    # 1. n이 3으로 나누어 떨어지면, 3으로 나눈다.
    if i % 3 == 0 :
        d[i] = min(d[i//3] + 1, d[i])
    # 2. n이 2로 나누어 떨어지면, 2로 나눈다.
    if i % 2 == 0 :
        d[i] = min(d[i//2]+1, d[i])

print(d[n])