백준 1034. 램프

https://www.acmicpc.net/problem/1034

1034번: 램프

 

엄청 죽을 많이 쓴 문제였다.

처음에 재귀로 조합을 만드는 방식으로 풀어볼까 했는데 아무리 생각해도 시간초과가 나올것 같았다.

시간을 줄이는 방법을 계속 고민해보다가 K가 짝수일때 홀수일때에 따라 n개 중에 r을 선택하는 경우에서 r이 결정될것 같았는데 이이상 진행이 안돼서 다른 분들 코드를 봤다.

 

결론적으로 조합을 뽑는 방식으로는 풀수 없는 문제였다.

 

 

 

이 문제에서 구하는건 스위치를 모두 누르고 마지막에 모두 1이 되있는 행의 갯수다.

그런데 스위치를 누를때는 열이 바뀐다.

 

그말은 즉 우선 하나의 행만 생각해서 K번 스위치를 눌렀을때 해당 행이 모두 1이 되는지 안되는지 판단해볼수 있다.

• 우선 만약 행에서 0의 갯수가 K보다 크다면 당연히 해당 행은 모두 1로 만들수 없을 것이다. 

 

버튼을 홀수번 누르면 상태가 바뀌고, 짝수면 누르면 원래대로 되돌아온다.

따라서 잘생각해보면 결론적으로 다음이 나온다. 

• 행에서 0의 갯수가 짝수개면, K가 짝수여야 해당 행을 모두 1로 만들수 있다.
• 행에서 0의 갯수가 홀수개면, K가 홀수여야 해당 행을 모두 1로 만들수 있다.

 

이렇게 하나의 행을 모두 1로 만들수 있는지 없는지 판단 가능하다.

만약 i 행을 모두 1로 만들수 있다면 다른 행들중 i와 같은 패턴의 행은 모두 1로 만들수 있다는 의미다. 

따라서 i 행과 같은 행의 갯수를 카운트한다.

 

모든 행에 대해 위를 반복해서 최댓행의 갯수를 구하면 답이다.