Baekjoon 18111번 마인크래프트

문제

https://www.acmicpc.net/problem/18111

걸린 시간

02 : 49 : 28 실패

시간 초과 풀이

Python3

if __name__ == "__main__":
    # 집터의 세로 : N, 가로 : M, 인벤토리의 블록 : B
    N, M, B = map(int, input().split())

    house = []
    for i in range(0, N):
        tmp = list(map(int, input().split()))
        for j in tmp: 
            house.append(j)

    maximum = max(house)
    minimum = min(house)
    candidateBlock = []

    for standard in range(minimum, maximum + 1):
        distroyBlock = 0
        needBlock = 0
        time = 0
        for land in house:
            # 땅이 기준으로 정한 값 보다
            # 높을 때 (제거)
            block = land - standard
            if land > standard:
                distroyBlock += block
                time += block * 2
            # 낮을 때 (추가)
            elif land < standard:
                needBlock += abs(block)
                time += abs(block) * 1
            else:
                pass

        # 가지고 있는 블럭의 개수가 필요한 땅의 개수보다 많을 때
        if needBlock <= B + distroyBlock:
            # 걸린 시간과 높이를 리스트로 묶어 저장
            candidateBlock.append([time, standard])        

    # 시간 최소값을 가져옴
    bestTime = min(candidateBlock)[0]

    # 정답이 여러개일 경우 가장 큰 높이를 가져옴
    for i in candidateBlock:
        if i[0] == bestTime:
            bestStandard = i[1]

    print(bestTime, bestStandard)

가능한 경우의 수를 일일이 모두 탐색해보는 완전 탐색;브루트 포스(Brute-force) 문제이다.

최악의 경우 최소 반복 횟수가 257 * 500 * 500 = 64,250,250 번 이상이기 때문이다. Python3 으로는 통과할 수 없다.

옳은 풀이

Python3

if __name__ == "__main__":
    # 집터의 세로 : N, 가로 : M, 인벤토리의 블록 : B
    N, M, B = map(int, input().split())

    # 땅의 높이 : height 
    height = [0] * 257
    for i in range(0, N):
        tmp = list(map(int, input().split()))
        for j in tmp: 
            height[j] += 1

    # 높이 후보 : candidateBlock
    candidateBlock = []

    for standard in range(0, 257):
        distroyBlock = 0
        needBlock = 0
        time = 0
        for land in range(0, 257):
            # 땅이 기준으로 정한 값 보다
            # 높을 때 (제거)
            block = land - standard
            if land > standard:
                distroyBlock += block * height[land]
                time += block * 2 * height[land]
            # 낮을 때 (추가)
            elif land < standard:
                needBlock += abs(block) * height[land]
                time += abs(block) * 1 * height[land]
            else:
                pass

        # 가지고 있는 블럭의 개수가 필요한 땅의 개수보다 많을 때
        if needBlock <= B + distroyBlock:
            # 걸린 시간과 높이를 리스트로 묶어 저장
            candidateBlock.append([time, standard])

    # 시간 최소값을 가져옴
    bestTime = min(candidateBlock)[0]

    # 정답이 여러개일 경우 가장 큰 높이를 가져옴
    for i in candidateBlock:
        if i[0] == bestTime:
            bestStandard = i[1]

    print(bestTime, bestStandard)

높이가 0부터 256사이의 작은 범위의 값임을 이용해 중복되는 값을 배열의 인덱스를 사용하여 묶어주면 257 * 257 = 66,049 로 반복 횟수가 크게 줄어들게 된다.

앞으로 시간초과가 날 땐 가장 큰 테스트 케이스를 적용시켜보고 어느 부분이 문제인지 찾는 습관을 들여야겠다.

참고

• 2577번 숫자의 개수