[Algorithm] [Python] 백준/BOJ - 1463 _ 1로 만들기

1463 - 1로 만들기

문제 설명

---

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

---

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

---

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

제출 코드

---

from sys import stdin

n = int(stdin.readline())
calc_result = [n]
cnt = 0

def checker(arr):               # 연산 함수
    l = []
    for i in arr:
        l.append(i-1)           
        if i%3 == 0:
            l.append(int(i/3))
        if i%2 == 0:
            l.append(int(i/2))
    return l

while True:
    if n == 1:
        break
    tmp = calc_result           # 연산 결과값을 tmp에 저장
    calc_result = []            # 연산 결과 배열 초기화
    calc_result = checker(tmp)  # tmp를 인자로 받아 연산을 진행한 결과값을 calc_result에 저장
    cnt += 1
    if 1 in calc_result:
        break

print(cnt)

풀이 설명

---

DP 를 이용하여 풀어내는 문제다.

문제 설명에서는 정수 X에 사용할 수 있는 연산이 3가지 주어졌다. 다만 연산의 우선순위는 없이 그냥 연산만 3가지 주어졌다.

이 문제를 풀 때는 연산의 우선순위는 중요하지 않다. 주어진 정수에 따라 최적해를 구하기 위해 진행 해야 할 연산의 우선순위가 서로 다르다.

따라서, 주어진 정수에 대하여 3가지 연산 중 진행이 가능한 연산을 모두 진행한 결과값을 반환해주는 함수를 만든다.

이후 그 결과값을 다시 해당 함수의 인자로 사용하여 반복을 진행하며 결과값 중 1이 나오기 까지 걸린 연산의 횟수를 구한다.