[JAVA]백준 1244번: 스위치 켜고 끄기

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

1244번: 스위치 켜고 끄기

1. 문제 설명

 

문제

• 1부터 연속적으로 번호가 붙어있는 스위치들이 있다.
• 스위치는 켜져 있거나 '1', 꺼져 있는 상태 '0'이다.
• 학생 몇명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다.
• 학생들은 자신의 성별과 받은 수에 따라 스위치를 조작한다.
• 남학생의 경우 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다.
• 여학생의 경우 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다.
• 스위치들의 마지막 상태를 출력하라.

조건

• 스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다.
• 스위치 개수와 학생 수는 100 이하인 양의 정수

 

2. 풀이

 

 

문제 그대로 구현하면 된다.

 

스위치의 개수와 학생의 수가 100 이하이므로 완전 탐색을 하더라도 최대 100*100으로 충분히 문제 풀이가 가능하다.

 

스위치를 전환할 때는 "1-스위치"의 식을 통해서 스위치의 상태를 전환했다.

 

 

*로직

1. 남학생의 경우 자기가 받은 수의 배수일때 스위치 전환 (1-스위치)

2. 여학생의 경우 자기가 받은 수를 중심으로 움직이면서 좌우가 대칭인지 확인하고, 대칭이면 스위치 전환(1-스위치) 아닐 경우 탐색 종료

3. 한 줄에 20개씩 스위치 출력

 

3. 코드

// JAVA 11 , 메모리 : 14244KB, 시간 : 132ms

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int switchNum,studentNum,sep,swit;
        int[] status;

        switchNum = Integer.parseInt(br.readLine());
        status = new int[switchNum+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int x = 1; x <= switchNum; x++) {
            status[x] = Integer.parseInt(st.nextToken());
        }

        studentNum = Integer.parseInt(br.readLine());

        for (int x = 0; x < studentNum; x++) {
            st = new StringTokenizer(br.readLine());

            sep = Integer.parseInt(st.nextToken());
            swit = Integer.parseInt(st.nextToken());

            if(sep==1){
                // 남학생

                for(int y=swit;y<=switchNum;y+=swit){
                    status[y] = 1 - status[y];
                }

            }else{
                // 여학생

                status[swit] = 1 - status[swit];

                for(int y=1;swit-y>0 && swit+y<=switchNum;y++){
                    if (status[swit - y] == status[swit + y]) {
                        status[swit - y] = 1 - status[swit - y];
                        status[swit + y] = 1 - status[swit + y];
                    } else {
                        break;
                    }
                }
            }
        }

        for (int x = 1; x <= switchNum; x++) {
            if(x!=1 && x%20==1)
                bw.write("\n");
            bw.write(String.valueOf(status[x]) + " ");
        }

        bw.flush();


    }


}