백준 1244번 스위치 켜고 끄기 :: 마이구미

이 글은 백준 알고리즘 문제 1244번 "스위치 켜고 끄기" 를 풀이한다.

정올 초등부에서 출제된 문제로써, 단순 문제 이해를 통한 구현이다.

문제 링크 - https://www.acmicpc.net/problem/1244

1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. <그림 1>에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.

스위치 번호  ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 
스위치 상태   0  1   0  1   0   0   0  1
<그림 1>

남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. <그림 1>과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 <그림 2>와 같이 3번, 6번 스위치의 상태를 바꾼다.

스위치 번호  ① ② ③ ④ ⑤ ⑥ ⑦ ⑧
스위치 상태   0  1   1  1   0   1   0  1
<그림 2>

여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이 때 구간에 속한 스위치 개수는 항상 홀수가 된다.

예를 들어 <그림 2>에서 여학생이 3을 받았다면, 3번 스위치를 중심으로 2번, 4번 스위치의 상태가 같고 1번, 5번 스위치의 상태가 같으므로, <그림 3>과 같이 1번부터 5번까지 스위치의 상태를 모두 바꾼다. 만약 <그림 2>에서 여학생이 4를 받았다면, 3번, 5번 스위치의 상태가 서로 다르므로 4번 스위치의 상태만 바꾼다.

스위치 번호  ① ② ③ ④ ⑤ ⑥ ⑦ ⑧
스위치 상태   1   0  0   0  1   1   0  1

<그림 3>

문제는 크게 남자와 여자로 2가지로 분류할 수 있다.

그 후, 각각에 대해 다시 분류할 수 있다.

남자가 받은 수의 배수에 해당하는 스위치 번호의 상태를 바꾼다.

여자가 받은 수를 기준으로 좌우대칭이 여부를 판단한다.

1. 대칭이라면 대칭되는 번호들의 상태를 바꾼다.
2. 대칭이 아니라면, 받은 수의 스위치 번호만 상태를 바꾼다.

여자의 경우에 있어, 대칭 여부만 잘 판단하면 된다.

받은 수를 기준으로 인접한 양쪽이 다르다면 대칭을 이룰 수 없다.

또한 양쪽 끝의 번호(1, N)에 해당하는 수를 받는다면 대칭을 이룰 수 없다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2000/1244.java

private void solve() {
    int n = sc.nextInt();
    int[] array = new int[n + 1];
 
    for (int i = 1; i <= n; i++) {
        array[i] = sc.nextInt();
    }
 
    int t = sc.nextInt();
 
    while (t-- > 0) {
        int sex = sc.nextInt();
        int idx = sc.nextInt();
 
        if (sex == 1) {
            // 남 
            for (int i = idx; i <= n; i += idx) {
                array[i] = array[i] == 0 ? 1 : 0;
            }
        } else {
            if ((idx == 1 || idx == n) || array[idx - 1] != array[idx + 1]) {
                array[idx] = array[idx] == 0 ? 1 : 0;
            } else {
                int left = idx - 1;
                int right = idx + 1;
                array[idx] = array[idx] == 0 ? 1 : 0;
                while (left > 0 && right <= n) {
                    if (array[left] == array[right]) {
                        array[left] = array[left] == 0 ? 1 : 0;
                        array[right] = array[right] == 0 ? 1 : 0;
                        --left;
                        ++right;
                    } else {
                        break;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        System.out.print(array[i] + " ");
        if (i % 20 == 0) {
            System.out.println();
        }
    }
}