23058번 - 뒤집기 게임
그리디하게 문제를 접근했습니다.
모든 색을 백으로 바꾸는 경우와 흑으로 바꾸는 경우, 두가지로 나눠서 둘 중 최솟값을 출력하도록 했습니다.
모든 행과 열에 대해서 한 줄씩 탐색을 합니다.
바꿀 색(target)과 다른 색의 개수를 찾아서 가장 많은 행 또는 열을 찾습니다.
개수가 N의 절반 초과면 -> 한 줄 뒤집기
이하면 -> 다른 돌만 하나씩 뒤집기
이렇게 해서 문제를 풀었는데 반례를 모르겠습니다.
[자문자답]
40 1 1 01 0 0 01 0 0 00 1 1 0
wrong : 6
answer : 5
저도 똑같은 방법으로 풀다가 똑같은 부분에서 막힌것같은데 어떻게 해결하셨나요?ㅠ
풀이방법을 아예 바꿔야하나요?
@munhwas1140
해당 풀이는 틀린 풀이로 반례가 존재합니다.
그래서 문제를 다르게 접근했습니다.
N의 크기가 크지 않다는 점을 이용하면 쉽게 접근하실 것 같습니다!
댓글을 작성하려면 로그인해야 합니다.
kdr06006 2년 전
그리디하게 문제를 접근했습니다.
모든 색을 백으로 바꾸는 경우와 흑으로 바꾸는 경우, 두가지로 나눠서 둘 중 최솟값을 출력하도록 했습니다.
모든 행과 열에 대해서 한 줄씩 탐색을 합니다.
바꿀 색(target)과 다른 색의 개수를 찾아서 가장 많은 행 또는 열을 찾습니다.
개수가 N의 절반 초과면 -> 한 줄 뒤집기
이하면 -> 다른 돌만 하나씩 뒤집기
이렇게 해서 문제를 풀었는데 반례를 모르겠습니다.