1로 만들기 (BAEKJOON - 1463번)

안녕하세요 강민성입니다.

오늘은 오랜만에 알고리즘 문제를 들고 와봤습니다.

겨울방학 동안 백준 사이트에 있는 문제를 풀어보고자 하는데

좋은 문제가 있으면 많이 포스팅 하도록 하겠습니다.

오늘 소개할 문제는 1463번 '1로 만들기' 라는 문제 입니다.

문제부터 보도록 하겠습니다.

문제는 생각보다 간단합니다.

3가지 연산만 골고루 써서 1을 만들어 주면 되는 것이죠.

그래서 문제없이 코드를 작성하였습니다.

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

X 값에 입력값을 받은 후 이 값이 1이 될 때까지 반복합니다.

주어진 연산처럼 3으로 나누어지면 3으로 나누고 count를 1 증가,

2로 나누어지면 3으로 나누고 count를 1 증가,

둘 다 안되면 1로 빼고 count를 1 증가하는 방법으로 count를 계산하였습니다.

하지만 놀랍게도 바로 틀리고 말았습니다.

이럴 경우, 예외가 존재하더라고요.

input이 10인 경우를 생각해봅시다.

주어진 코드대로 라면, 10 -> 5 -> 4 -> 2 -> 1 다음과 같은 순서로 4번만에 1로 바꿀 수 있습니다.

하지만 순서를 조금 바꿔서 1을 먼저 빼고 시작한다면, 10 -> 9 -> 3 -> 1 다음과 같이 3번만에 할 수 있는거죠.

결국 다시 처음부터 코드를 작성해야 했습니다.

그래서 택한 방법은 dynamic programming 입니다.

X값이 들어왔을 때, 3으로 나눈 경우, 2로 나눈 경우, 1로 뺀 경우, 각각의 count들을 계산하여

최소값을 택하는 방법으로 말이죠.

코드를 보도록 하겠습니다.

X = int(input())
 
answer = [0,0]
 
for i in range(2,X+1):
    temp = []
    temp.append(answer[i-1])
    if i % 3 == 0:
        temp.append(answer[i//3])
    if i % 2 == 0:
        temp.append(answer[i//2])
    answer.append(min(temp)+1)
 
print(answer[X])

먼저 answer에는 0을 두 개 넣어주었습니다.

첫 번째 0은 answer 이라느 list의 index와 해당하는 숫자가 같아지도록 하기 위해 자리수를 채워주는 역할을 합니다.

두 번째 0은 1을 1로 만드는데 0번의 방법이 필요한 것을 의미하는 것이죠.

이제 저 answer list에 계속 해서 값을 채워 줄 것입니다.

index 2에는 2를 1로 만들기 위해 2로 한 번 나눠주면 되니까 1이 들어올 것입니다.

그리고 최종적으로 answer[X] 값이 우리가 원하는 값이 될 것입니다.

그러면 answer list를 채워 나가는 과정을 살펴보도록 하겠습니다.

2부터 X까지 반복을 하게 됩니다.

임시 list temp를 만들어주고 temp에는 매 반복마다 1~3개의 원소가 들어갑니다.

원하는 값보다 1 작은 값에 해당되는 횟수는 무조건 들어가고

2와 3으로 나눈 수에 해당하는 값에 해당하는 횟수는 나눠질 경우 선택적으로 들어가게 됩니다.

그 후 temp의 최소값을 구하고 여기서 한 번의 수행을 더 거치면 우리가 원하는 값이 되는 것입니다.

마무리

다이나믹 프로그래밍 문제 중에서도 쉬운 편에 속한다는 생각이 들지만

아직 낯설고 어려운 것 같습니다.

방학동안 열심히 공부 해보겠습니다.

모두 화이팅 :)