글 읽기 - 시간초과 질문드립니다.[파이썬]

parksjin01 5년 전 0

TC는 전부 맞았고 9%에서 시간초과가 계속 발생합니다.

어디서 중복으로 계산되는 부분이 있는지 잘 모르겠습니다. ㅜㅜㅜ

할 수 있는 만큼 최적화 시켰다고 생각했는데, 어디를 고쳐야하는지 잘 모르겠습니다 ㅠㅠ

import sys

flag = 987654321

def possible(laddle, row, column, last_height):

    # 가장 마지막에 놓인 사다리
    row = max(row, last_height)

    for x in range(column):
        cur_x = x
        for y in range(row):
            if cur_x < column - 1 and laddle[y][cur_x] != 0:
                cur_x += 1
            elif cur_x > 0 and laddle[y][cur_x - 1] != 0:
                cur_x -= 1

        # 만약 x에서 출발한 것이 다른 위치에 도착한다면, 거짓을 반환한다.
        if cur_x != x:
            return False
    return True

def finding(laddle, idx, cnt, row, column, last_height, last_available_height):
    global flag
    
    # 만약 현재 사다리로 모든 출발지와 모든 도착점이 같다면 flag를 cnt로 맞춘다.
    if possible(laddle, row, column, last_height):
        flag = cnt
        return cnt
    
    # 4개 이상 선택해야 하면 -1로 반환한다.
    if idx == 0:
        return 987654321
    
    # 현재 선택된 값보다 더 큰 값이 필요하다면 -1을 반환한다.
    if cnt > flag:
        return 987654321

    res = 987654321
    for y in range(last_height, last_available_height):
        for x in range(column - 1):
            if laddle[y][x] == 1:
                continue
            elif x == 0 and x + 1 < column - 1 and laddle[y][x + 1] == 1:
                continue
            elif x == column - 1 and laddle[y][x - 1] == 1:
                continue
            elif x + 1 < column - 1 and (laddle[y][x + 1] == 1 or laddle[y][x - 1] == 1):
                continue

            laddle[y][x] = 1
            res = min(res, finding(laddle, idx - 1, cnt + 1, row, column, y, last_available_height))
            laddle[y][x] = 0

    return res

laddle = []
column, setted, row = list(map(int, sys.stdin.readline().strip("\n").strip(" ").split(" ")))

for _ in range(row):
    laddle.append([0] * (column - 1))

last = 0
for _ in range(setted):
    y, x = list(map(int, sys.stdin.readline().strip("\n").strip(" ").split(" ")))
    laddle[y - 1][x - 1] = 1
    if last < y:
        last = y

res = finding(laddle, 3, 0, row, column, 0, min(row, last + 3))
if res > 3:
    print(-1)
else:
    print(res)

indioindio 5년 전 0

pypy3로 제출하면 말씀하신 9%의 벽은 넘지만, 나중에 틀렸습니다가 뜨네요.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.[파이썬]

parksjin01 5년 전 0

indioindio 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말