-
백준 1244번 스위치 켜고 끄기 :: 마이구미알고리즘 풀이/수학 2018. 3. 6. 19:59반응형
이 글은 백준 알고리즘 문제 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, N)에 해당하는 수를 받는다면 대칭을 이룰 수 없다.
Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2000/1244.java
12345678910111213141516171819202122232425262728293031323334353637383940414243444546private 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();}}}cs 반응형'알고리즘 풀이 > 수학' 카테고리의 다른 글
백준 14890번 경사로 :: 마이구미 (0) 2018.04.06 백준 10837번 동전 게임 :: 마이구미 (0) 2018.04.01 백준 1236번 성 지키기 :: 마이구미 (0) 2018.03.06 백준 2505번 두 번 뒤집기 :: 마이구미 (1) 2018.02.05 백준 2564번 경비원 :: 마이구미 (0) 2018.01.29