mminky's

* 문제
https://www.acmicpc.net/problem/11729

[ 해결 원리 ]
하노이탑 개념에 대해 그림으로 쉽게 설명해두었으니 참고하면 좋을 것 같다 :)
https://mminky.tistory.com/116

[ 코드 ]
**하노이탑 파이썬 - 시간초과가 떴다면**
print(count) 대신 print(2**n - 1) 를 해라!
-> 하노이탑의 총 옮긴 횟수는 2^n - 1으로 정해져 있다.
(하지만 개인적으로 옮길 때 마다 count를 증가시켜서 총 count를 출력하는 게 맞다고 생각한다.
근데 그렇게 하면 시간 초과가 된다..)

import sys input=sys.stdin.readline n = int(input()) #count = 0 #옮긴 횟수 #ans='' def hanoi(disk_num,from_peg,to_peg,tmp_peg): global count,ans if(disk_num==1): print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg,to_peg) # count += 1 return hanoi(disk_num-1,from_peg,tmp_peg,to_peg) print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg, to_peg) # count += 1 hanoi(disk_num-1,tmp_peg,to_peg,from_peg) print(2**n - 1) #count를 하니 시간 초과 뜸 # (처음)1 에서 (최종)3으로 이동함 # 2는 거치는 곳일 뿐! hanoi(n,'1','3','2') #print(count) #print(ans)

[ 결과 ]
와.. 진짜 시간초과 너무한거 아니냐고....
몇 번을 시도해서 결국 통과되었다.. 너무해..

[ 원래 코드 ]

a,b,c=map(int,input().split())
num=0

for i in range(0,a):
    for j in range(0,b):
        for k in range(0,c):
            print(i,j,k)
            num+=1

print(num)

-> 시간초과에러가 발생했다..

심지어 정답 코드랑도 동일하던데..

답변에는 새벽시간에 내라, 정답의 복잡도는 O(N^3)이다 이런 말 밖에 없었다..

[ 고친 코드 ]

print()함수는 한 번 실행되는 시간이 오래 걸리기 때문에 시간초과가 걸렸다고 한다.

그래서 다음과 같이 string에 결과를 추가해서 마지막에 한 번 출력하는 방향으로 진행했다. (@ji.o.n.e의 도움으로..)

a,b,c=map(int,input().split())
num=0
answer=''

for i in range(0,a):
    for j in range(0,b):
        for k in range(0,c):
            answer+=str(i)+' '+str(j)+' '+str(k)+'\n'
            num+=1

print(answer,num,sep='')

[ 결과 ]

그래도 여전히 시간이 많이 걸리기는한다.

아무튼 해결!!

[ Code Up 해당 문제 ]

codeup.kr/problem.php?id=6083

※ 제 글이 도움이 되었다면 공감 부탁드려요 :)