백준 6459 만취한 상범(Java)

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

6359번: 만취한 상범

---

 

해석 및 팁

 

---

 

이 문제의 핵심은 방의개수만큼 배열을 선언해서 배열의 값이 0이면 닫혀있고 1이면 열려있다는것을 표현하는것이다. 첫번째 for문을 통해 테스트케이스인 t만큼 돌아주고 두번째 for문으로 1부터 방의개수인 n만큼 돌아주고 세번째 for문으로 배수알때 문을 열고 닫으면 된다. 마지막으로 배열의값이 1인것의 개수를 세어서 출력해주면 된다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
  
    int t = sc.nextInt();

    for(int i = 0; i < t; i++) {
      int count = 0;
      int n = sc.nextInt();
      int[] check = new int[n+1];                     //n번째 방을 확인하기위한 배열 선언
      for(int j = 1; j <= n; j++) {
         for(int k = 1; j * k <= n; k++) {            //n까지의 수중 배수 확인
           if(check[k * j] == 0) check[k * j] = 1;    //0 이면 1로 바꿔주고 1이면 0으로 바꿔준다
           else check[k * j] = 0;
         }
      }
      for(int j = 1; j <= n; j++) {
        if(check[j] == 1) count++;                     //1이면 열려있으므로 탈출가능하다.
      }
      System.out.println(count);
    }
    
  }  
}