[백준 17554] City of Lights [Java]

문제

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

 

---

풀이

처음에는 켜져있는 N개의 전구에 대해 K번 동안 N이하의 i배수 번째의 전구들을 토글할 때 최대한 많이 꺼진 전구의 수를 구하는 문제다.

처음에는 전구를 전부 켜주고,

        boolean[] light = new boolean[N];
        Arrays.fill(light, true);

K개의 i를 입력 받아, i의 배수들을 전부 토글하면 된다.

        int res = 0;
        while (K-- > 0) {
            final int i = Integer.parseInt(br.readLine());

            // Solve
            int cur = -1;
            while ((cur += i) < N) light[cur] = !light[cur];

이후 각 i에 대해 전구가 가장 많이 꺼진 수를 찾으면 된다.

            int sum = 0;
            for (boolean b : light) {
                if (!b) ++sum;
            }
            res = Math.max(res, sum);
        }

        // Output
        System.out.println(res);
    }
}

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/17554.java