글 읽기 - 시간 초과, 어디서 시간을 더 줄여야 할까요?

csm06063 2년 전 0

원래 O(n^3)이었던 걸, 대충 O(n^2)로 줄여봤습니다.

여기서 시간 복잡도를 더 줄일 수 있을까요? 계속 시간 초과가 뜨네요 ㅠ

(참고로 2차원 배열을 1차원으로 늘여서 작성했습니다.)

from sys import stdin

input = stdin.readline
world = list()
n, m, blocks = map(int, input().split())
for _ in range(n): world.extend(list(map(int, input().split())))
answer = 0
height = max(world)
totalBlocks = sum(world)

while totalBlocks != world[0] * n * m:
    neededBlocks, diggingBlocks = n * m * height - totalBlocks, 0
    # 현재 층까지의 빈 공간을 가지고 있는 블럭으로 채울 수 있을 경우
    if neededBlocks <= blocks:
        # 빈 공간을 채우는 게 더 빠를 경우
        if neededBlocks / blocks >= 0.5:
            blocks -= neededBlocks
            answer += neededBlocks
            for i in range(n * m):
                if world[i] != height: world[i] += 1
            height += 1
            totalBlocks += neededBlocks
        # 현재 층을 아예 파내는 게 더 빠를 경우
        else:
            diggingBlocks += n * m - neededBlocks
            blocks += diggingBlocks
            answer += diggingBlocks * 2
            for i in range(n * m):
                if world[i] == height: world[i] -= 1
            height -= 1
            totalBlocks -= diggingBlocks

    # 현재 층까지의 빈 블럭 > 가지고 있는 블럭일 경우: 현재 층을 파내고 다시 계산
    else:
        for i in range(n * m):
            if world[i] == height:
                diggingBlocks += 1
                world[i] -= 1
        blocks += diggingBlocks
        answer += diggingBlocks * 2
        height -= 1
        totalBlocks -= diggingBlocks

print(f"{answer} {world[0]}")

choko100 1년 전 0

안녕하세요, 이 문제는 추가 시간이 없어서 python 3 로는 조금 빡빡해서요. 혹시 pypy 3 로 제출해보시는 건 어떨까요?

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

문제

문제

출처

ICPC

시간 초과, 어디서 시간을 더 줄여야 할까요?

csm06063 2년 전 0

원래 O(n^3)이었던 걸, 대충 O(n^2)로 줄여봤습니다.

여기서 시간 복잡도를 더 줄일 수 있을까요? 계속 시간 초과가 뜨네요 ㅠ

(참고로 2차원 배열을 1차원으로 늘여서 작성했습니다.)

choko100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말