글 읽기 - 사다리조작 시간초과질문(조합으로 푸는거아닌가요?)

zxaq15 3년 전 0

이 문제 조합으로 푸는거 아닌가요??

인터넷에 있는 코드랑 별 다를게 없는거같은데 9%에서 자꾸 시간초과가나네요;

import sys


def check():
    for i in range(1, n+1):  # i는 시작점
        cur = i              # 사다리를 타면 cur값이 바뀌게 된다.
        for j in range(1, h+1):
            if (j, cur) in ladders:
                cur += 1
            elif (j, cur-1) in ladders:
                cur -= 1
        if cur != i:
            return False
    return True


def dfs(lv, x, y):
    global answer
    if lv > answer or lv > 3:
        return
    if check():
        answer = min(answer, lv)
        return
    
    for i in range(x, n+1):
        start = y if x == i else 1
        for j in range(start, h+1):
            if (j, i) not in ladders and (j, i-1) not in ladders:
                ladders.add((j, i))
                dfs(lv+1, i, j+1)
                ladders.remove((j, i))


#세로, 가, 가로선개수
n, m, h = map(int, input().split())
ladders = set()  # 놓아진 사다리들
for _ in range(m):
    a, b = map(int, input().split())
    ladders.add((a, b))

answer = sys.maxsize

dfs(0, 1, 1) # 문제대로 1부터 시작하게 코드작성

if answer == sys.maxsize:
    print(-1)
else:
    print(answer)

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

문제

문제

출처

ICPC

사다리조작 시간초과질문(조합으로 푸는거아닌가요?)

zxaq15 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말