[백준(python)] 1463번: 1로 만들기

1463번: 1로 만들기

문제

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

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

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

입력

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

출력

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

풀이

X = int(input())
count = [0 for i in range(X+1)]
count[1] = 0

for i in range(2, X + 1):
    count[i] = count[i - 1] + 1  

    if i % 3 == 0:
        count[i] = min(count[i], count[i // 3] + 1)
    if i % 2 == 0:
        count[i] = min(count[i], count[i // 2] + 1)

print(count[X])

설명

• count
  각 인덱스에 1을 만들기위한 연산 횟수를 저장
  1이 1을 만들기 위한 연산 횟수는 0

• count[i] = count[i - 1] + 1
  1빼는 방법임!! 바로 그 전 수의 횟수에 +1만 해주면 됨

• 처음 if문
  1빼는 방법과, 3으로 나누는 방법 중 더 적은 횟수
  3으로 나누는 방법이란? ex) i가 6이라면 i가 2일때의 횟수 +1

• 두번째 if문
  1빼는 방법과, 2로 나누는 방법 중 더 적은 횟수