백준 1463번 문제 풀이

1로 만들기 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.15 초 (하단 참고)

128 MB

146022

45774

29037

31.841%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: cyj101366, jugol
• 어색한 표현을 찾은 사람: dbfldkfdbgml
• 데이터를 추가한 사람: dynamiseus, jooa7878

알고리즘 분류

• 다이나믹 프로그래밍

시간 제한

• Python 3: 1.5 초
• PyPy3: 0.7 초
• Python 2: 1.5 초
• PyPy2: 0.7 초

출처)

 www.acmicpc.net/problem/1463

---

 

 

백준 1463번 문제이다. 풀고나니까 엄청 간단한 문제이지만 나는 이틀동안 고민해서 풀었다 ㅠㅠ

일단 내가 생각했었던 흐름대로 설명해보겠다.

 

가장 먼저 이 문제를 보고 어떻게 풀지 고민했었으나 규칙성이 보이지 않았다.

 

그래서 일단 일일이 하나씩 1부터 30까지 정수를 대입해보면서 규칙성을 찾아보려고 했다.

 

처음에는 숫자를 3(n-2), 3(n-1), 3n 으로 나눠서 확인해보고

 

그 다음에는 숫자를 3^a * 2^b - c  이런식으로 지수승으로 확인해봤다.

 

 

 

하지만 문제는 풀리지 않았다

 

그러다가 몇몇 숫자들 사이에서 힌트를 얻었다.

 

11 같은 경우 2와 3으로 나뉘지 않아 -1 을 하면 10이 되고

 

10은 아까 해보니까 3이 나왔으니 11은 4겠다....

 

 

 

여기서 힌트를 찾은 것이다.

 

만약 정수 n 이 주어진다면 정수 n -1 까지의 결과 값만 안다면  n-1, n / 3, n / 2 이 3가지 값중에서(3과 2로 나누어 떨어진다는 가정하에)

 

가장 작은 값  + 1(왜냐하면 3을 나누던, 2로 나누던, 1을 빼던 한번의 연산을 한 것이니까) 을 하면 답이겠다. 라는 결과를 얻었다.

 

 

 

그래서 코드를 작성했다.

 

일단 1부터 10까지의 결과값을 사전에 만들어 정의해두고

 

정수 n이 주어지면 11부터 n-1까지의 결과값을 사전에 추가하는 반복문을 만들었다.

 

그리고 for 반복문이 실행될 때 마다 if를 사용하여 경우의수에 따라서 다르게 진행 되도록 했다

 

1. 정수 i 가 3과 2로 나누어 떨어지는지, 

 

2. 정수 i 가 3으로만 나누어 떨어지는지,

 

3. 정수 i 가 2으로만 나누어 떨어지는지,

 

4. 정수 i 가 나누어 떨어지지 않는지

 

 

완성된 코드는 아래와 같다.

 

n = int(input())

box = {
    1 : 1,
    2 : 1,
    3 : 1,
    4 : 2,
    5 : 3,
    6 : 2,
    7 : 3,
    8 : 3,
    9 : 2,
    10 : 3
}

for i in range(11, n+1):
     # 경우의 수 1. 2와 3으로 나누어 떨어질 때
    if i % 3 == 0 and i % 2 == 0:
        list = [box[int(i / 2)], box[int(i / 3)], box[i - 1]]
        box[i] = min(list) + 1
    elif i % 3 ==0 and i % 2 != 0:
        list = [box[int(i / 3)], box[i - 1]]
        box[i] = min(list) + 1
    elif i % 3 != 0 and i % 2 == 0:
        list = [box[int(i / 2)], box[i - 1]]
        box[i] = min(list) + 1
    else:
        box[i] = box[i-1] + 1

print(box[n])