[백준 - 6359번] 만취한 상범 - 자바(JAVA) 정리 및 해설 & 1일 1DP -6일차

안녕하세요. 오늘 풀어 볼 문제는 만취한 상범입니다. 

6359번: 만취한 상범

DP라고 하기에는 애매한 부분이 있긴하지만, 그래도 처음에 풀기에 무난한 문제입니다.

어떤식으로  풀었는지?

방을  int로 만들고 (물론, int로 안만들어도 됩니다.) 방을 열었으면 1 방문을 닫았으면 0으로 처리하고 모든 배수별로 모든 문을 열고 닫으면 방이 1인 걸 찾아서 카운팅을 합니다.  그러면 정답.  

/** 2020. 2. 25. 오후 3:09:46
 * @author ventulus95
 */
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class No6359_TheDrunkJailer {
	
	static int room[] = new int [120];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i =0; i<T; i++){
			int n = Integer.parseInt(br.readLine());
			Arrays.fill(room, 0);
			for(int j=1; j<=n; j++){
				for(int k =1; k*j<=n; k++){
					if(room[k*j]==0){
						room[k*j]++;
					}
					else{
						room[k*j]--;
					}
				}
			}
			int cnt =0;
			for(int j=1; j<=n; j++){
				if(room[j]==1){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
	}

}