백준 1244 - 스위치 켜고 끄기
Updated:
Java
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>
입력으로 스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어진다. 학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램을 작성하시오.
접근 방법
남자인 경우와 여자인 경우를 나누어 조건에 따라 구현한다.
구현
남자의 경우 단순하게 받은 값을 계속 배수로 증가 시키며, 그 위치의 스위치를 변환한다.
여자의 경우 받은 위치에서 양 옆으로 하나씩 이동을 하며, 대칭이면 스위치를 변환하고 대칭이 아닌 위치면 바로 종료하도록 한다.
코드
import java.io.*;
import java.util.*;
import java.util.*;
import java.io.*;
public class Main {
public static void main(String []args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int n = stoi(br.readLine());
ArrayList<Integer> sw = new ArrayList<>();
// 초기 스위치 입력 시작
sw.add(-1);
stk = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
sw.add(stoi(stk.nextToken()));
}
int sn = stoi(br.readLine());
int curN, idx = 1, savedN;
while(sn-- != 0) {
stk = new StringTokenizer(br.readLine());
idx = 1;
// 남자인 경우
if(stoi(stk.nextToken()) == 1) {
curN = stoi(stk.nextToken());
savedN = curN; // 각 숫자의 배수
while(savedN <= n) {
sw.set(savedN, change(sw.get(savedN))); // 숫자의 배수만큼 인덱스를 증가시키며 전환시킨다.
savedN += curN;
}
}
// 여자인 경우
else {
curN = stoi(stk.nextToken());
sw.set(curN, change(sw.get(curN))); // 입력 받은 위치의 스위치를 전환한다.
while(true) { // 양 옆으로 이동하면서, 각 값이 대칭인지 확인한다.
if(curN - idx == 0 || curN + idx > n || (sw.get(curN - idx) != sw.get(curN + idx)))
break;
// 대칭이면 양 스위치를 전환한다.
sw.set(curN - idx, change(sw.get(curN - idx)));
sw.set(curN + idx, change(sw.get(curN + idx)));
idx++;
}
}
}
for(int i = 1; i <= n; i++) {
System.out.print(sw.get(i));
if(i % 20 == 0) // 20개 단위로 잘라서 출력한다.
System.out.println();
else
System.out.print(" ");
}
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
static int change(int i) {
if(i == 0)
return 1;
else
return 0;
}
}
총평
난이도
⭐⭐★★★
후기
문제에 사족이 많아, 이해하는데 조금 시간이 걸렸다.
문제를 이해하고 나면 쉬운 문제.
개선할 점
없
