글 읽기 - 파이썬 18111 무엇을 틀렸을까요?

zmellonz 3년 전 1

우선 제 코드를 python으로 돌리면 시간초과가 뜹니다.

그 부분은 나중에 코드를 손본다 하더라도 pypy3에서 돌릴 때에는 시간초과가 아닌 틀렸습니다가 나오는데

제 코드에서 어느 부분이 틀렸는지 모르겠습니다 ㅠㅠ

게시판에서 뒤져본 반례들은 전부 통과하는데 말이죠..

a,b,c=map(int,input().split())
land=[]
for _ in range(a):
    land+=list(map(int,input().split()))
    
min_height=min(land)
max_height=max(land)
cost=[]
# 최소층~ 최대층 검색
for i in range(min_height,max_height+1):
    time=0
    block=c
    for j in land:
        # land 가 더 크면 깎아야지 -> 2코
        if j > i:
            time+=(j-i)*2
        # i 가 더 높으면 추가!
        elif j < i:
            #block 이 부족하면? 
            if block<(i-j):
                time=float('inf')
                break
            else:
                block-=(i-j)
                time+=(i-j)
    cost.append([time,i])
#cost 오름차순 height 내림차순
cost.sort(key=lambda x:[x[0],-x[1]])
print(cost[0][0], cost[0][1])

zmellonz 3년 전 0

혹시 추가적으로 시간 초과 부분도 아시는 분 계시면 조언 부탁드립니다.

input을 readline으로 바꿔도 시간초과가 뜹니다.

ks2515 3년 전 4

```

입력 :

3 4 0
1 2 3 4
5 6 7 8
9 10 11 12

출력 :

132 1

정답 :

57 6

```

코드를 열심히 보진 않았지만, 높은 곳의 블록을 캐서 낮은 곳을 메꾸는 경우를 생각하지 않아서 생긴 문제 같아 보여요.

시간초과는 최대 500 x 500 = 250000 칸을 최대 256번 반복해서 다 둘러보기 때문입니다.

모든 칸을 다 둘러보는 방법이 아니라 다른 방법을 쓴다면 시간초과도 통과하실 겁니다.

zmellonz 3년 전 0

감사합니다 ㅠㅠ 싹다 갈아엎었네요 시간초과는 조금ㄷ 더 봐야겠지만 통과한걸로 만족했습니다 일단..

wjd5269 3년 전 0

KS2515 님 작성자님 감사합니당 저도 여기서 틀렸네요 허허..

ahmg1216 2년 전 0

와 저도 여기서 틀렸네요

sayori 2년 전 0

저도 여기서 틀렸습니다...

정말로 감사합니다...

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

문제

문제

출처

ICPC

파이썬 18111 무엇을 틀렸을까요?

zmellonz 3년 전 1

zmellonz 3년 전 0

ks2515 3년 전 4

zmellonz 3년 전 0

wjd5269 3년 전 0

ahmg1216 2년 전 0

sayori 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말