Python3
문제
https://www.acmicpc.net/problem/1244
키워드
- 구현
- 시뮬레이션
문제 풀이
문제 요구사항
학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램
- 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다.
- 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.
변수 및 함수 설명
- n : 스위치 개수
100 이하인 양의 정수 - switch : 각 스위치의 상태
- p : 학생수
100 이하인 양의 정수 - s : 학생의 성별
남학생은 1로, 여학생은 2 - num : 학생이 받은 수
스위치 개수 이하인 양의 정수
- change(idx) : 스위치 상태를 바꾸는 함수
풀이
- 남학생일 경우, num부터 스위치 개수에서 num만큼 증가시키며 스위치를 바꾼다.
- 여학생일 경우, num에 해당하는 스위치를 바꾼다.
- num 기준 양쪽을 바꾸므로 이분탐색법을 수행한다
- num - i가 1보다 작거나 num + 1이 n을 넘어가면 반복문 종료
- 대칭된 스위치의 상태가 같으면 각 스위치의 상태를 바꾼다.
최종 코드
def change(idx):
if switch[idx] == 1:
switch[idx] = 0
else:
switch[idx] = 1
return
n = int(input())
switch = [-1] + list(map(int, input().split()))
p = int(input())
for _ in range(p):
s, num = map(int, input().split())
if s == 1:
for i in range(num, n+1, num):
change(i)
elif s == 2:
change(num)
for i in range(n//2):
if num - i < 1 or num + i > n: break
if switch[num - i] == switch[num + i]:
change(num + i)
change(num - i)
else: break
for i in range(1, n+1):
print(switch[i], end=' ')
if i % 20 == 0:
print()피드백
인덱스는 0으로 시작하는데 스위치 번호는 1부터 매겨져 있기 때문에 인덱스 0 값은 더미로 담아준다.
num - i < 1 or num + i > n 조건을 num - i > 1 and num + i < n로 해서 (예제 기준) 1, 5번 스위치가 안 바꼈다.
I mean