(파이썬)백준 알고리즘 1463번 1로 만들기

백준 알고리즘 저지 1463번 문제 (https://www.acmicpc.net/problem/1463)

 

 

1, 2, 3번 방법을 조합하여 1을 만드는 문제.

가장 적은 횟수를 찾는 문제인데 나는 1, 2, 3번 방법을 저장하고 중복을 제거하고, 그 결과에 대한 1, 2, 3을 수행하고 ... 1이 나오면 멈추도록함.

최적해의 시간 복잡도는 잘 모르겠지만 그에 비에 공간 복잡도가 안좋게 설계 된 코드일듯..

 

훗날 더 좋은 방법이 떠오르길

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
·¬
Q=[int(input())]¬
count=0¬
def·doit(Qu):¬
····temp=[]¬
····for·i·in·Qu:¬
········temp.append(i-1)¬
········if·i%3==0:¬
············temp.append(i/3)¬
········if·i%2==0:¬
············temp.append(i/2)¬
····temp=set(temp)¬
····temp=list(temp)¬
····return·temp¬
¬
while·True:¬
····temp=Q[:]¬
····Q=[]¬
····Q=doit(temp)¬
····count+=1¬
····if·min(Q)==1:¬
········break¬
print(count)¬
¶
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX