1463_1로만들기

문제는 더보기!

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

 

개인적으로 디게 어려운 문제였다... 삽질도 많이했고

 

풀이방법을 보면 우선 들어온 N+1만큼의 리스트를 만들어 둔다. 그래야 입력의 순서값과 index의 값이 일치하게 된다.

그 후 1부터 천천히 올라가면서 리스트를 채워나가면 된다. 리스트에는 '횟수'를 넣을 것이다.

즉 index가 숫자, 리스트가 횟수가 된다.

 

비교할 값은 3가지이다.

 

1. 이전단계의 값 + 1

2. 3으로 나누어진값의 횟수 +1

3. 2로 나누어진 값의 횟수 + 1

 

 

[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 2, 3, 2, 0, 0, 0, 0]
[0, 0, 1, 1, 2, 3, 2, 3, 0, 0, 0]
[0, 0, 1, 1, 2, 3, 2, 3, 3, 0, 0]
[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 0]
[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]
3

 

위는 예시인 10을 가지고 리스트를 채워가는 모습을 출력해본 값이다. 

1인경우에는 답이 0이기 때문에 2부터 시작하였다.

 

 

N = int(input())
lst = [0] * (N+1)

for i in range(2,N+1):
    lst[i] = lst[i-1] + 1
    if i%3 ==0:
        lst[i] = min(lst[i],lst[i//3]+1)
    if i%2 ==0:
        lst[i] = min(lst[i],lst[i//2]+1)


print(lst[-1])