BOJ 14754 - Pizza Boxes

문제

백준 온라인 저지 - 14754번

풀이 과정

피자박스들이 주어질 때 앞과 옆에서 봤을 때 최대 높이에 변화가 없는 한에서 없앨 수 있는 피자박스의 개수를 구하는 문제입니다.

행과 열을 기준으로 탐색했을 때 가장 높은 위치에 있는 피자들을 남겨놓고 나머지는 없애면 됩니다.

따라서 O(N^2) 의 시간 복잡도로 원하는 개수를 구할 수 있습니다.

코드

import sys


N, M = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def remove_pizza():
    check = [[0] * M for _ in range(N)]

    for x in range(N):
        max_idx = 0
        for y in range(M):
            if board[x][max_idx] < board[x][y]:
                max_idx = y
        check[x][max_idx] = 1
    for y in range(M):
        max_idx = 0
        for x in range(N):
            if board[max_idx][y] < board[x][y]:
                max_idx = x
        check[max_idx][y] = 1

    return check


def solution():
    answer = 0
    check = remove_pizza()

    for x in range(N):
        for y in range(M):
            if not check[x][y]:
                answer += board[x][y]

    return answer


print(solution())