글 읽기 - 파이썬) 시간 초과 질문(마인크래프트 문제)

osh1795 2년 전 0

제가 이 코드로 pypy3는 통과하지만 python3에서는 1퍼센트에서 바로 시간초과가 발생합니다. (시간: 756ms)

1. pypy3에서는 통과하지만, python3에서는 통과하지 않는 이유는 무엇일까요?

2. 저보다 빠른 시간에 통과한 코드랑 비교해봤을 때, 제 코드와 큰 차이는 없는데 2배정도 더 걸리는 원인을 알 수 있을까요??

import sys
input = sys.stdin.readline

    #Input
n,m,b = map(int,input().split())    #b: 인벤토리
case = []   #블록 input 저장
max_block = 0   #input중 max
min_block = 256 #input중 min
sum_block = 0   #input 총합
for i in range(n):  #입력받기
    lst = list(map(int,input().split()))
    if max(lst) > max_block:    #최대 층
        max_block = max(lst)
    if min(lst) < min_block:    #최소 층
        min_block = min(lst)
    sum_block += sum(lst)       #총 갯수
    case.append(lst)

ans = -1    #정답 - 시간
ans_block = False   #정답 - 층수
for blocks in range(max_block,min_block -1,-1):
    if blocks * m * n > sum_block +b:   #제작 가능성 판단
        continue    #기존 인벤토리로 해당 층으로 매끈하게 못하면 pass
    time_block = 0      #걸리는 시간 초기화
    flag = False        #true면 탐색 종료(이미 최소값보다 커질때 True로)
    for i in range(n):
        for j in range(m):
            if case[i][j] < blocks: #기준보다 낮음 >> 쌓기(1초)
                time_block += blocks - case[i][j]
                if time_block >= ans and ans != -1:
                     #이미 최소값 초과 & 최초의 데이터가 아님
                    flag = True #이미 최소값 오버로 패스 판단
                    break
            elif case[i][j] > blocks: #기준보다 높음 >> 제거(2초)
                time_block += 2 * (case[i][j] - blocks)
                if time_block >= ans and ans != -1:
                     #이미 최소값 초과 & 최초의 데이터가 아님
                    flag = True #이미 최소값 오버로 패스 판단
                    break
        if flag:    #falg = True면 이미 최소값을 오버했다는 뜻
            break

    if flag == False:  
        if ans == -1:
            ans = time_block
            ans_block = blocks
        else:
            if time_block < ans:
                ans = time_block
                ans_block = blocks

print(ans,ans_block)

dkeya 2년 전 0

저도 pypy에서는 통과하는데 python3에서는 왜 통과가 안될까요...

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

문제

문제

출처

ICPC

파이썬) 시간 초과 질문(마인크래프트 문제)

osh1795 2년 전 0

dkeya 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말