[백준 1736번] 쓰레기 치우기 (Python3)

def clean():
  last = 0
  for i in range(N):
    end = last
    for j in range(last,M):
      if board[i][j]:
        end = j
    for j in range(last,end+1):
      board[i][j] = 0
    last = end

N,M = map(int,input().split())
board = [[*map(int,input().split())] for i in range(N)]
result = 0
while sum(map(sum,board)):
  clean(); result += 1
print(result)

그리디 알고리즘 문제이다.

처음에는 정렬 문제라고 생각했다. 그러나 단순정렬로 해결하면 반례가 존재하는 것을 알게되었다.

 

풀이를 설명하면,

1. clean 함수를 사용해서 가장 첫째 줄부터 쓰레기를 탐색한다.

2. 현재 줄에서 0부터 탐색하여 가장 마지막으로 쓰레기가 발견된 칸을 end로 저장한다.

3. 0~end까지의 쓰레기를 치운다.

4. 다음 줄부터는 0부터가 아닌 end 부터 탐색한다. 마찬가지로 쓰레기가 발견되면 end를 찾고 (end1이라 두면) end~end1까지의 쓰레기를 치운다.

5. clean 함수를 쓰레기가 모두 없어질 때까지 실행한다.

 

가장 첫째 줄부터 그리디하게 쓰레기를 순차적으로 지우면서 몇 번 실행해야하는지를 구하면 해결되는 문제이다.

 

 

오늘의 교훈) 다양한 문제를 풀자