글 작성자: 개발섭

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

 

6359번: 만취한 상범

문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고

www.acmicpc.net

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);
		}
	}

}