반응형
처음엔 예제입력의 2와 10을 기준으로 먼저 생각해 보았다.
'1을 뺀다'로 연산 횟수를 한 번 사용하더라도 '2로 나눈다'에서 '3으로 나눈다'로 바뀔 수 있으면 이득이라고 생각했다.
그래서 10의 경우에 10은 2의 배수이지만 1을 뺐을 때 9(3의 배수)가 되기 때문에 10에서 바로 2로 나누는 트리인
10 -> 5 -> 4 -> 2 -> 1 보다
10 -> 9 -> 3 -> 1 이 더 효율적인 방법이 되는 것이었다.
10 -> 5 -> 4 -> 2 -> 1 이 방법에서 중간에 등장하는 4의 경우만 해도 아주 작은 숫자일지라도 1을 빼면 3이 되기 때문에
4 -> 3 -> 1 로
4 -> 2 -> 1 과 비교해서 연산 횟수가 추가되진 않기 때문에 4보다 큰 수들은 당연히 이 방식대로면 3의 배수로 만들기만 하면 횟수에서 이득을 볼 수 있을것이었다.
그렇게 생각해서 짠 실패 코드이다.
<실패 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
n = int(input())
time = 0
while n != 1:
if n%3 == 0:
n = n//3
time = time+1
elif n%2 == 0:
if (n-1)%3 == 0:
n = n-1
time = time+1
else:
n = n//2
time = time+1
else:
n= n-1
time = time+1
print(time)
|
수 많은 입력값 중에 내가 생각하지 못한 예외가 있을거란 생각이 들어
내가 따로 생각하지 않아도 되게끔, 컴퓨터에서 모든 경우의 수를 직접 다 해보고 가장 먼저 1에 도착한 녀석의
결과만 알려주는 코드를 작성했다.
<성공 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
from copy import copy as copy
n = int(input())
results = set()
results.add(n)
time = 0
def cal_all(n):
results.add(n-1)
if (n%3 ==0):
results.add(n//3)
elif (n%2 == 0):
results.add(n//2)
while(min(results) != 1):
temps = copy(results)
results = set()
time += 1
for i in temps:
cal_all(i)
print(time)
|
반응형
'Python > 알고리즘' 카테고리의 다른 글
| 알고스팟 (백준 1261, 파이썬) (0) | 2019.08.31 |
|---|---|
| 이모티콘 (백준 14226, 파이썬) (0) | 2019.08.31 |
| 보석 도둑 (백준 1202, 파이썬) (0) | 2019.08.21 |
| 재귀호출로 최댓값 구하기 (모두의 알고리즘 with 파이썬 4-2) (0) | 2019.07.04 |
| 열 개씩 끊어 출력하기 (백준 11721, 파이썬) (0) | 2019.07.02 |