백준 6603번(로또) 파이썬

https://www.acmicpc.net/problem/6603

6603번: 로또

이 문제는 분명 백트리킹 알고리즘도 사용했고 예제 출력도 잘 나오는데 

25%에서 시간초과 탈락을 했다;;

아무리 찾아도 이유를 모르겠어서 사이트에 질문을 남겼는데

다행이 자고 일어나니 어떤 고수분께서 답을 알려주셨다.

아래는 틀렸던 답안이다.

 

<25% 시간초과 코드>

import sys
input = sys.stdin.readline

def dfs():
    if len(ans) == 6 and ans == sorted(ans):
        print(' '.join(map(str,ans)))
        return
    for i in range(len(lotto)):
        if visited[i]:
            continue
        visited[i] = True
        ans.append(lotto[i])
        dfs()
        ans.pop()
        visited[i] = False
while True:
    lotto = list(map(int,input().split()))
    if lotto[0] == 0:
        break
    visited=[False]*(lotto[0])
    ans = []
    del lotto[0]
    dfs()
    print()

위의 코드에서 잘못된 점을 찾았다면 당신은 고수입니다;;

위의 코드에서 틀린점은 if len(ans) == 6  and ans == sorted(ans) 다.

이유는 뒤의 조건이 충족 되지 않을경우 ans의 길이가 7이상으로 늘어나 버리기 때문이다.

그래서 25%에서 시간초과가 났던 것이다.

그래서 바로 코드를 수정했다

 

<정답 코드>

import sys
input = sys.stdin.readline


def dfs():
    if len(ans) == 6:
        if ans == sorted(ans):
            print(' '.join(map(str,ans)))
        return
    for i in range(len(lotto)):
        if visited[i]:
            continue
        visited[i] = True
        ans.append(lotto[i])
        dfs()
        ans.pop()
        visited[i] = False

while True:
    lotto = list(map(int,input().split()))
    if lotto[0] == 0:
        break
    visited=[False]*(lotto[0])
    ans = []
    del lotto[0]
    dfs()
    print()

바로 조건문을 아래 하나 추가해 버리는 것이다.

이러니까 1초만에 통과;;ㅋㅋ

하아... 전혀 생각하지도 못한 이유였다.

알고리즘 너무 어렵다...