[개쉬운 풀이] 백준 1244 스위치 켜고 끄기

https://www.acmicpc.net/problem/1244

문제

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

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

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

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

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

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

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

입력으로 스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어진다. 학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램을 작성하시오.

생각

1. 단순한 구현 문제이다.
2. 남자와 여자의 프로세스를 나누어서 해결하면 된다.
3. 남자는 숫자의 배수만큼 계속 상태를 바꿔야한다.
4. 여자는 해당 스위치를 바꾸고 양옆 상태가 같으면 바꾸고 다르면 스톱

풀이

input()

1. state를 1 ~ N까지 담는다.
2. 성별과 스위치 숫자를 같이 담는다.

changeState()

1. state를 바꾼다.

boy()

1. 현재 스위치 숫자를 저장한다. tmp
2. while문을 활용하여 tmp값을 num의 i배 만큼 곱하여 갱신하고
3. state를 바꾼다.

girl()

1. 현재 숫자 스위치를 바꾼다.
2. while 문을 통해 양옆을 확인한다.
3. 인덱스 범위를 넘어가지 않도록 한다.
4. 같으면 둘다 state바꾼다.
5. 다르면 거기서 stop한다.
6. 왜냐하면, 부여받은 스위치 숫자를 '기준'으로 양옆 최대 구간을 구하는 것 이므로

sol()

1. 학생의 숫자를 기준으로 for 반복문
2. 성별에 맞게 boy()와 girl() 실행한다.

#include <iostream>
#include <vector>
using namespace std;

struct T{
    int sex, switchs;
};

int N;
int M;
vector<int> state;
vector<T> students;

void input(){
    cin >> N;
    state = vector<int>(N+1);
    //1 ~ N까지 저장
    for(int i = 1; i <= N; i++){
        cin >> state[i];
    }

    cin >> M;
    students = vector<T> (M);
    for(int i = 0; i < M; i++){
        cin >> students[i].sex >> students[i].switchs;
    }
}

void changeState(int idx){
    state[idx] = !state[idx];
}

void boy(int num){
    int i = 2;
    int tmp = num; //num = num * (i++) 실수하지 않기
    while(tmp <= N){
        changeState(tmp);
        tmp = num * (i++);
    }
}

void girl(int num){
    //자기 자신 state도 변환해야한다.
    changeState(num);
    int left = num - 1;
    int right = num + 1;
    while(left >= 1 && right <= N){ //인덱스 범위 확인하기
        if(state[left] == state[right]){ 
            changeState(left--);
            changeState(right++);
        }
        else break; //num 기준으로 최대 구간을 구해야 하므로 다르면 바로 break
    }
}

void print(){
    int p;
    for(int i = 1; i <= N; i++){
        cout << state[i] << " ";
        //출력 형식 신경쓰기
        if(i % 20 == 0) cout << endl;
    }
    cout << endl;
}

void sol(){
    for(int i = 0; i < M; i++){
        T tmp = students[i];
        //성별에 따라 프로세스 실행
        if(tmp.sex == 1) boy(tmp.switchs);
        else if(tmp.sex == 2) girl(tmp.switchs);
    }
    print();
}

int main(){
    input();
    sol();
    return 0;
}

틀렸던 원인

1. 출력형식 -> 20번째인데 코드 순서로 19번째부터 줄바꿈함
2. girl의 while문 조건의 인덱스 범위 실수