풀이: 백준.1034.램프

[changicho]

1034. 램프

링크

난이도	정답률(_%)
Gold V	33.657

설계

시간 복잡도

N과 M은 최대 50까지이다. K 는 최대 1,000 까지 이므로 모든 경우를 시도해보는 경우

50^1000 번이 소요되므로 제한시간 내에 불가능하다.

따라서 스위치를 껏다 켜는 규칙을 이용해 풀이한다.

공간 복잡도

입력은 한줄씩 주어지므로 string 배열로 입력을 관리한다.

불을 켜는 규칙

모든 경우를 시도해 볼 수 없으므로, 각 행별로 순회를 하며 스위치를 바꿧을 때 얼마나 많은 정답이 나올 수 있는지 검사한다.

1. 먼저 현재 행에서 0의 개수를 센다.
2. 0의 개수가 K보다 작거나 같으며, K가 홀수인경우 0의 개수도 홀수, 짝수인경우 마찬가지로 짝수인지 판별한다.
3. 2번 조건을 만족하지 못하는 경우 이 행에서는 불가능하다.
4. 만족하는 경우 행을 다시 순회하며 현재 행과 같은 것들을 count한다.
5. count한 값이 answer보다 큰 경우 answer를 갱신한다.

이방법은 각 행이 같은것들이 존재하는 경우, 그 행들의 0인 부분만 스위치를 켜면 정답의 후보가 될 수 있음을 이용한다.

먼저 모든 행의 전구가 켜져야 하고, 꺼진 전구의 개수보다 스위치가 더 많은 경우 불가능하다.

또한 K와 0의개수가 서로 홀수, 짝수인지 비교하는 것은

꺼진 전구를 홀수번 반복하면 켜지고, 짝수번 반복하면 꺼지기 때문이다.

따라서 켜야할 남은 전구들을 전부 키기 위해 홀수와 짝수를 검사한다.

for (int y = 0; y < N; y++) {
  int zeroCount = 0;
  for (char c : lamps[y]) {
    if (c == '0') zeroCount++;
  }
  int sum = 0;
  if (zeroCount <= K && zeroCount % 2 == K % 2) {
    for (int temp_y = 0; temp_y < N; temp_y++) {
      if (lamps[y] == lamps[temp_y]) {
        sum++;
      }
    }
  }
  answer = max(sum, answer);
}

정리

내 코드 (ms)	빠른 코드 (ms)
0	0

고생한 점