글 읽기 - 시간초과 질문

bjh99 2년 전 0

위의 코드는 정답처리가 되고, 밑의 코드는 시간초과가 나오는데, 둘의 시간 차이가 어디서 나오는건지 알 수 있을까요..?

import sys

input = sys.stdin.readline

N = int(input().rstrip())

result = 0
candies = []
def dfs(x):
    global result
    if x == N:
        result += 1
        return
    
    for i in range(N):
        check = True

        if len(candies) != 0:
            for candi in candies:
                if candi[0] == x or candi[1] == i or abs(candi[0] - x) == abs(candi[1] - i):
                    check = False
                    break
        if check:
            candies.append((x, i))
            dfs(x+1)
            candies.pop()

dfs(0)
print(result)
                
                
-------------------------------------------------------------------------
import sys

input = sys.stdin.readline

N = int(input().rstrip())
queens = []
cnt = 0

def check(x, y):
    for queen in queens:
        if queen[1] == y or abs(queen[0] - x) == abs(queen[1] - y):
            return False
    return True

def dfs(depth):
    global cnt
    if depth == N:
        cnt += 1
        return
    for i in range(N):
        if check(depth, i):
            queens.append([depth, i])
            dfs(depth+1)
            queens.pop()

for i in range(N):
    queens.append([0, i])
    dfs(1)
    queens.pop()

print(cnt)
    

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문

bjh99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말