[BOJ] 1080

less than 1 minute read

행렬

1080번 https://www.acmicpc.net/problem/1080

Greedy algorithm을 사용하는 문제입니다.
기준을 세우지 않는다면 이것도 신경쓰이고 저것도 신경쓰이고 너무 어려울텐데
왼쪽 위 기준으로 3 × 3부분행렬을 만들어 나올 수 있는 모든 부분행렬을 살펴본다면
지금 기준이 되는 칸은 이후의 부분행렬에서 바꿀 수 없는 칸임을 알 수 있습니다.
따라서, 기준이 되는 칸이 뒤집어져야 하는 칸인지를 판단해 바꿔야 하는 칸이라면
해당 부분행렬을 모두 뒤집어주는 식으로 진행해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1080.cpp

Categories:

Updated:

Leave a comment