백준 12852번 : 1로 만들기 2 in Python

12852번: 1로 만들기 2

 

www.acmicpc.net

이 문제는 주어진 자연수를 3으로 나누거나, 2로 나누거나, 1을 빼서 가장 적은 연산으로 1을 만들려고 할 때 연산의 최소 횟수와 연산 과정을 구해야 하는 문제이다.

만약 연산 최소 횟수만 구한다고 하면 dynamic programming을 이용해 1부터 N까지 차례대로 위 문제를 풀면서 접근하면 되지만 연산 과정도 구해야 하기 때문에 이를 저장할 배열을 하나 더 추가한다.

그래서 dynamic programming을 구현할 때는 우선 길이가 N+1인 배열 dp와 record를 만들고 배열의 인덱스에 대해 1부터 N까지 순회하면서, dp[i]를 dp[i-1], dp[i//2] (i가 2로 나누어 떨어질 때), dp[i//3] (i가 3으로 나누어 떨어질 때) 중 가장 작은 값에 1을 더한 값으로 변경하고, 가장 작은 값에 해당하는 인덱스를 record[i]에 저장한다. 즉, record[i]는 숫자 i가 어느 연산을 해야 가장 적은 연산으로 1에 도달할 수 있는지를 알려준다.

이를 반복해 i가 N까지 도달하면 dp[N}은 N을 주어진 연산들을 통해 1에 도달할 수 있는 가장 적은 연산 횟수를 의미하게 되고, 만약 연산 과정을 알고 싶은 경우 record 배열에서 인덱스 N을 시작으로 그 인덱스에 해당하는 원소를 record의 인덱스로 찾아가면서 계속 따라가면 된다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
# dynamic programming 구현을 위한 배열
dp = [0 for _ in range(N+1)]
# 가장 적은 연산 과정을 기록하기 위한 배열
record = [i for i in range(N+1)]
for i in range(2, N+1):
    # 1을 빼는 연산
    dp[i] = dp[i-1] + 1
    record[i] = i-1
    # 3으로 나누어 떨어지는 경우 3으로 나누는 연산
    if i%3 == 0 and dp[i//3] + 1 < dp[i]:
        dp[i] = dp[i//3] + 1
        record[i] = i//3
    # 2로 나누어 떨어지는 경우 2로 나누는 연산
    if i%2 == 0 and dp[i//2] + 1 < dp[i]:
        dp[i] = dp[i//2] + 1
        record[i] = i//2
# 가장 적은 연산 횟수를 나타낸다.
cnt = dp[N]
print(cnt)
# 연산 과정 출력을 위한 함수
def print_record(n):
    if n == 1:
        return "1"
    return str(n) + " " + print_record(record[n]) 
print(print_record(N))