kdr06006   2년 전

그리디하게 문제를 접근했습니다.

모든 색을 백으로 바꾸는 경우와 흑으로 바꾸는 경우, 두가지로 나눠서 둘 중 최솟값을 출력하도록 했습니다.

모든 행과 열에 대해서 한 줄씩 탐색을 합니다.

바꿀 색(target)과 다른 색의 개수를 찾아서 가장 많은 행 또는 열을 찾습니다.

개수가 N의 절반 초과면 -> 한 줄 뒤집기

                   이하면 -> 다른 돌만 하나씩 뒤집기

이렇게 해서 문제를 풀었는데 반례를 모르겠습니다.

kdr06006   2년 전

[자문자답]

4
0 1 1 0
1 0 0 0
1 0 0 0
0 1 1 0

wrong : 6

answer : 5

munhwas1140   2년 전

저도 똑같은 방법으로 풀다가 똑같은 부분에서 막힌것같은데 어떻게 해결하셨나요?ㅠ

풀이방법을 아예 바꿔야하나요?

kdr06006   2년 전

@munhwas1140

해당 풀이는 틀린 풀이로 반례가 존재합니다.

그래서 문제를 다르게 접근했습니다.

N의 크기가 크지 않다는 점을 이용하면 쉽게 접근하실 것 같습니다!

댓글을 작성하려면 로그인해야 합니다.