문제
N×M 격자에 동전이 놓여있다. (i,j)를 선택하면 (0,0)부터 (i,j)까지의 직사각형 영역의 모든 동전이 뒤집힌다. 모든 동전을 뒤면(0)으로 만드는 최소 연산 횟수를 구하라.
입력
첫째 줄에 N, M, 이후 N줄에 동전의 상태 (0: 뒤면, 1: 앞면)가 주어진다.
출력
최소 뒤집기 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 2 11 11 | 1 |
풀이
우하단부터 좌상단으로 순회하며, 앞면(1)인 동전을 만나면 (0,0)~(i,j) 영역을 뒤집는다. 우하단부터 처리하면 이미 처리한 칸에 영향을 주지 않아 그리디가 성립한다.
- (N-1, M-1)부터 (0, 0) 방향으로 역순 순회한다
- 현재 칸이 앞면(1)이면 flip 함수로 (0,0)~(i,j) 영역을 뒤집고 카운트를 증가시킨다
- flip은 해당 영역의 모든 동전을 토글한다
- 모든 칸을 처리한 뒤 카운트를 반환한다
핵심 아이디어: 우하단부터 처리하면 현재 칸의 상태가 최종 상태가 되므로, 앞면일 때만 뒤집으면 최소 횟수가 보장된다.
코드
import sys
input = sys.stdin.readline
def flip(x, y):
for i in range(x + 1):
for j in range(y + 1):
if coin[i][j]==1:
coin[i][j]=0
else:
coin[i][j]=1
N, M = map(int, input().split())
coin = [list(map(int, list(input().strip()))) for _ in range(N)]
cnt = 0
for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if coin[i][j]:
cnt += 1
flip(i, j)
print(cnt)복잡도
- 시간: O(N² × M²)
- 공간: O(NM)