[BOJ] 1463번: 1로 만들기

merong·2023년 3월 24일
1

BOJ

목록 보기
1/1

문제

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

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

입력

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

출력

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

예제 입력

10

예제 출력

3 (10->9->3->1)

풀이

이전에 풀었던 이코테 1로 만들기와 거의 흡사한 문제이다.
제목은 '1로 만들기'인데, top-down⬇ 방식으로 푸는 것보다 아예 1부터 시작하는 bottom-up⬆ 방식이 훨씬 수월하게 풀린다.

아래 엉성하게 그린 가지치기를 보자.

겹치는 수들이 많이 생겨 top-down⬇으로 하다가 처음에는 일단 계산을 하고, 앞에서 맞닥뜨렸던 수일 경우 그 수의 최소 연산 횟수를 불러오면 되지 않을까 하는 생각이 들게 된다. 💭

하지만 각각의 수가 나왔을때부터 1이 될 때까지의 과정을 일일이 관찰하기엔 꽤 많은 비용이 소요된다.
하나의 루트가 아니라 여러 가지 루트로 쪼개지니 각 루트로 현재까지의 연산 횟수를 계속해서 보내줘야 하고, 연산 결과 매번 새로운 수가 나오면 해당 수 또한 1이 될 때까지의 과정을 관찰해줘야 하기 때문이다. 딱 봐도 구현이 굉장히 짜증날 것 같은 예감이 든다...😵😖

그림을 보면 어쨌거나 우리는 1부터 X까지의 모든 수를 살펴봐야 한다는 것을 알 수 있다. 왜냐하면 계속해서 1로 빼기만 하는 경우도 존재하기 때문이다. 여기서 🍀HINT🍀를 얻어서, 거꾸로 1부터 최소 연산 횟수를 구하도록 한다.

구한 최소 연산 횟수는 항상 최소임을 보장한다.
어떤 수 N에서 연산 가능한 모든 경우에서, 각각의 연산 결과 M은 무조건 N보다 작고, M을 1로 만드는 최소 연산 횟수는 이미 앞에서 결정되었기 때문에,
(M들의 최소 연산 횟수들 중 가장 작은 값+1) ➡ N을 1로 만드는 최소 연산 횟수

<과정 예시>

d 리스트에 최소 연산 횟수를 저장한다. 진한 값(더 작은 값)이 해당 인덱스에 저장된다.

d[1]: 시작점이니 0
d[2]: 2에서 1을 빼면 1 ➡ d[1]+1(1) / 2에서 2를 나누면 1 ➡ d[1]+1(1)
d[3]: 3에서 1을 빼면 2 ➡ d[2]+1(2) / 3에서 3을 나누면 1 ➡ d[1]+1(1)
d[4]: 4에서 1을 빼면 3 ➡ d[3]+1(2) / 4에서 2를 나누면 2 ➡ d[2]+1(2)
.
.
.
d[9]: 9에서 1을 빼면 8 ➡ d[8]+1(3) / 9에서 3을 나누면 3 ➡ d[3]+1(2)
d[10]: 10에서 1을 빼면 9 ➡ d[9]+1(3) / 10에서 2를 나누면 5 ➡ d[5]+1(4)

코드

def toone(x):
    d[1]=0
    for i in range(2,x+1):

        #1 빼기
        d[i]=d[i-1]+1

        #2 나누기
        if i%2==0:
            d[i]=min(d[i], d[i//2]+1)

        #3 나누기
        if i%3==0:
            d[i]=min(d[i], d[i//3]+1)

    return d[x]


n=int(input())
d=[0]*(n+1)
print(toone(n))
  • 함수를 따로 구현하여 풀었지만, for문만 써서 풀어도 된다.

백준 1463: 1로 만들기

profile
매일매일이 새로운 시작점

0개의 댓글