#1_ 1로 만들기(백준 1463번, 파이썬 풀이)

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.

입력

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

출력

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

예제 입력 : 2

예제 출력 : 1

예제 입력2 : 10

예제 출력2 : 3

---

처음에는 알고리즘을 단순하게 생각했다가 바로 틀려버린 문제입니다.

먼저 최종 정답으로 통과한 코드는 아래와 같습니다.

a = int(input())
count = 0
minimum=[a]
def cal(a):
    list = []
    for i in a:
        list.append(i-1)
        if i%3 == 0:
            list.append(i/3)
        if i%2 == 0:
            list.append(i/2)
    return list
 
while True:
    if a == 1:
        print(count)
        break
    temp = minimum[:]
    minimum = []
    minimum = cal(temp)
    count +=1
    if min(minimum) == 1:
        print(count)
        break

처음에는 단순히 반복문과 조건문을 이용해서 문제를 풀었습니다.

a = int(input())
count = 0
 
while True:
    if a==1:
        print(count)
        break
    
    if a%3 == 0:
        a = a/3
    elif a%2 == 0:
        a = a/2
    else:
        a = a-1
    count = count + 1

이렇게 해서 풀었더니 가차 없이 틀리더군요..

뭐가 틀렸을까 고민해보다가 예제입력2로 주어진 10이라는 숫자가 보였습니다.

처음에 작성한 코드에 10을 입력하면 count는 4로 출력됩니다.

하지만 문제에서 최소한의 연산을 이용하라고 했음에 유의해야합니다.

위의 코드대로라면 10 -> 5 -> 4 -> 2 -> 2 순서로 연산이 되어 연산 회수는 총 4번입니다.

하지만, 10에서 2로 나누지 않고 1을 빼는 연산을 우선으로 한다면?

10 -> 9 -> 3 -> 1 순서로 연산이 진행되어 연산 회수는 총 3번입니다.

이러한 결과를 도출하기 위해 고민했습니다.

연산에 우선순위를 두는 것은 소용이 없습니다.

10이라는 입력에 대해 올바른 출력을 위해 1을 빼는 것을 우선 순위로 처리한다면?

6이라는 숫자를 입력했을때, 6 -> 3 -> 1 의 순서가 아닌, 6 -> 5 -> 4 -> 2 -> 1 의 순서로 연산이 될 것 입니다.

그렇다면, 입력한 숫자로 세가지 연산을 모두 수행하여(1,2번 연산은 가능할 때만) 그 결과 값을 리스트로 저장하고, 그 리스트안에 있는 각각의 숫자들을 다시 세가지 연산 모두를 수행하도록 하고, 각 루프 한번당 count를 1씩 증가시키면 어떨까요?

정리해본다면, 세가지 연산을 모두 처리하는 함수 cal()을 만들어서 cal()함수를 재귀적으로 호출하는 방법입니다.

그래서 처음에 언급한 코드를 구현하게 되었습니다.

a = int(input())
count = 0
minimum=[a]
def cal(a):
    list = []
    for i in a:
        list.append(i-1)
        if i%3 == 0:
            list.append(i/3)
        if i%2 == 0:
            list.append(i/2)
    return list
 
while True:
    if a == 1:
        print(count)
        break
    temp = minimum[:]
    minimum = []
    minimum = cal(temp)
    count +=1
    if min(minimum) == 1:
        print(count)
        break

위의 코드를 보시면, 처음에 minimum이라는 리스트를 선언하고 초기값으로 입력값을 넣습니다.

그리고 4번 라인부터 12번 라인까지는 3가지 연산을 수행하고 그 결과값을 배열로써 반환하는 함수입니다.

15번에서 입력값이 1일때를 처리하고, 이후 minimum배열을 복사해서 temp 배열을 구성하고, minimum 배열은 다시 비우도록 합니다. 단순히 하나의 배열에 계속 넣게되면 메모리 초과가 될까봐 이런식으로 구현하였습니다.

그리고 temp를 cal()함수의 인자로 넣어 연산을 수행하고, 그 결과값 배열을 minimum으로 받습니다.

그리고 연산 count를 1 증가시키고, minimum에 있는 값중 최소값이 1일때 count값을 출력하며 반복문을 마무리하도록 합니다.