[BOJ] 스위치 켜고 끄기 - 1244 (S4)

시간 제한	메모리 제한
2 초	128 MB

문제

1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이고 1은 켜져있음을, 0은 꺼져있음을 나타낸다.

학생 몇 명이 스위치를 조작하는데, 학생들은 성별에 따라 다음과 같이 스위치를 조작한다:

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

스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어질 때, 모든 학생이 스위치를 조작한 후 스위치들의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 셋째 줄에는 학생수가 주어진다. 학생수는 100 이하인 양의 정수이다. 넷째 줄부터는 한 줄에 한 학생의 성별, 학생이 받은 수가 주어진다. 성별은 남학생은 1로, 여학생은 2로 나타낸다. 학생이 받은 수는 스위치 개수 이하인 양의 정수이다.

출력

스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다.

풀이

이 문제는 시뮬레이션 문제로, 주어진 규칙에 따라 스위치 상태를 변경하면 된다.

접근 방법

성별에 따른 스위치 조작 방법:

남학생 (gender = 1)

받은 수의 배수 위치에 있는 모든 스위치를 토글한다.

• 받은 수가 3이면: 3번, 6번, 9번, … 스위치를 토글

여학생 (gender = 2)

받은 수를 중심으로 좌우 대칭인 가장 긴 구간을 찾아 모두 토글한다.

• 중심 스위치는 무조건 토글
• 좌우로 확장하면서 대칭인지 확인
• 대칭이 아니거나 범위를 벗어나면 중단

코드

def toggle_switch(switches, N, gender, num):
    if gender == 1:
        # 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다.
        for i in range(num - 1, N, num):
            switches[i] = (switches[i] + 1) % 2
    else:
        # 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다.
        num -= 1
        switches[num] = (switches[num] + 1) % 2

        i = 1
        while num - i >= 0 and num + i < N:
            if switches[num - i] != switches[num + i]:
                break

            switches[num - i] = (switches[num - i] + 1) % 2
            switches[num + i] = (switches[num + i] + 1) % 2
            i += 1
    return switches

N = int(input())
switches = list(map(int, input().split()))

M = int(input())
for _ in range(M):
    gender, num = map(int, input().split())
    switches = toggle_switch(switches, N, gender, num)

for i in range(N // 20 + 1):
    print(*switches[i*20:(i + 1)*20])

코드 설명

toggle_switch 함수

남학생 처리:

for i in range(num - 1, N, num):
    switches[i] = (switches[i] + 1) % 2

• num-1부터 시작 (0-indexed)
• num 간격으로 스위치를 토글
• (x + 1) % 2로 0↔1 토글

여학생 처리:

num -= 1  # 0-indexed로 변환
switches[num] = (switches[num] + 1) % 2  # 중심 토글

i = 1
while num - i >= 0 and num + i < N:
    if switches[num - i] != switches[num + i]:
        break
    switches[num - i] = (switches[num - i] + 1) % 2
    switches[num + i] = (switches[num + i] + 1) % 2
    i += 1

• 먼저 중심 스위치를 토글
• 좌우로 한 칸씩 확장하며 대칭 확인
• 대칭이면 토글하고 계속, 아니면 중단

출력 처리

for i in range(N // 20 + 1):
    print(*switches[i*20:(i + 1)*20])

• 한 줄에 20개씩 출력
• print(*list)로 공백으로 구분하여 출력

시간 복잡도

• 남학생 한 명당: O(N / num) ≈ O(N)
• 여학생 한 명당: O(N) (최악의 경우 전체 탐색)
• M명의 학생: O(M × N)
• N, M ≤ 100이므로 최악의 경우 10,000번의 연산으로 충분히 빠르다.

주의 사항

1. 인덱스 변환: 문제는 1-indexed이지만 배열은 0-indexed이므로 변환이 필요하다.
2. 여학생 대칭 조건: 좌우가 같은 상태일 때만 대칭으로 판단한다. (둘 다 0이거나 둘 다 1)
3. 출력 형식: 한 줄에 정확히 20개씩 출력해야 한다.
4. 범위 체크: 여학생이 좌우로 확장할 때 배열 범위를 벗어나지 않도록 주의한다.

예제 분석

스위치 개수: 8
초기 상태: 0 1 0 1 0 0 0 1

학생 1 (남학생, 3):

• 3, 6번 스위치 토글
• 결과: 0 1 1 1 0 1 0 1

학생 2 (여학생, 3):

• 3번 중심으로 대칭 확인
• 2-3-4가 대칭 → 토글
• 1-2-3-4-5 대칭 아님 → 중단
• 결과: 0 0 0 0 0 1 0 1

이런 식으로 각 학생의 조작을 순차적으로 적용하면 된다.