1034 c++1 BOJ 1034 - 램프 https://www.acmicpc.net/problem/10341차 시도처음 그리디를 이용하여 0의 개수가 가장 많은 열을 스위치 작동시키는 방법을 구상했다.O(N*M)이 걸렸지만 스위치 작동 후의 0을 구하는 과정과 켜진 행을 찾는 구간 때문에 시간 초과가 발생했다.더 빠른 방법을 구상해보기로 했다.2차 시도우선 규칙이 보였다.한 행에서 0의 개수가 k보다 크면, 해당 행은 완전히 켜질 수 없다.한 행의 0의 개수와 k의 홀짝이 다르면, 해당 행은 완전히 켜질 수 없다.2번의 경우, 밑에 예시로 보자3 30101011014일 경우, 2번째 열을 홀수번 킬 때 2,3번 행이 완전히 켜지게 된다.그러나 k가 짝수이기 때문에 2,3번 행은 처음과 같은 상태가 된다.3 30101011013반면, k가 홀수가.. 2024. 10. 28. 이전 1 다음