[Backjoon] 6359번 문제 - 만취한 상범

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생들이 구금되어있다.

그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. 같은 방식으로 n번의 라운드를 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

풀이

우선 테스트 케이스만큼 while문을 반복하도록 설정한다.

다음으로 감옥의 갯수를 설정해야하는데, 열려있는 방은 true, 닫힌 방은 false로 하기위해 boolean 배열을 사용했다.

 따라서 마지막은 true의 갯수만 찾으면 되는것이다.

감옥은 1부터 시작하므로 배열의 사이즈는 외부에서 받아온 size+1을 해줬다.

어차피 0번째 감옥은 건드리지 않고 계속 false 값이다.

그리고 반복문을 순환하며 열린문은 닫고 닫힌문은 열게한다.

라운드가 끝나고 현재 배열에 열려있는(true값인) 배열의 개수를 출력한다.

import java.util.Arrays;
import java.util.Scanner;
 
/**
 * Created by homr on 2017. 5. 27..
 */
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T!=0){
            int size = sc.nextInt()+1;
            int count=0;
            boolean[] arr = new boolean[size];
            Arrays.fill(arr,false);
 
            for(int i = 1; i < size; i++){
                for(int j = 1; j*i < size; j++){
                    arr[j*i] = arr[j*i]==true ? false:true;                                              
                }
            }
 
            for(int i = 0; i<size; i++){
                if(arr[i]==true){
                    count++;
                }
            }
 
            System.out.println(count);
 
            T--;
        }
 
    }
}