[백준 Java] 6359 다이나믹프로그래밍

[문제]

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

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

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

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

[풀이]

규칙은 int형 dp배열에 값을 담아놓고 불러오는 형식이라면
dp[1] = 1라운드에 1개의 방을 열고끝나는 값. dp[1] = 1;
(편의상 dp[0] = 0; 으로두었다.)
마찬가지로 dp[2] = 1. 1라운드는 2개의방을열고 2번째방을 잠궜기때문이다.
즉 , dp[n] = dp[n-1] + n번째방 이 2~n 사이의 값으로 나누어지는 경우가 총
홀수개이면 close, 짝수면 open으로 코드에서는 check 지역변수를사용.

import java.util.Scanner;

public class Main {
	private static int dp[];
	private static int input[];

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int t = scanner.nextInt();
		input = new int[t];
		
		dp = new int[101];
		
		//인풋배열만듬
		for(int i = 0 ; i < t ; i ++) 
			input[i] = scanner.nextInt();
		

		
		//출력
		for(int i = 0 ; i < t ; i ++)
			System.out.println(dinamic_programing(input[i]));
		

	}
	//인자로받은 룸갯수로 dp실행
	private static int dinamic_programing(int number) {
		dp[0] = 0; //안씀
		dp[1] = 1;
		dp[2] = 1;
		
		if(number == 1)
			return dp[1];
		
		if(number == 2)
			return dp[2];
		
		if(dp[number] != 0) //이미 존재하면 리턴
			return dp[number];
		
		
		
		for(int i = 3 ; i <= number ; i ++) { //3부터 room까지실행
			int check = 0; // 홀수일때 close 짝수일때open

			
			dp[i] = dp[i - 1]; // 바로앞의 dp를먼저불러옴
			//이 위에부분은 i = 3일때 i-1 = 2 이므로 무조건 불러올수있음
			//botoom - up 방식이므로 오류날일없다.

			for (int j = 2; j <= i; j++) { // i보다 작거나 같은 모든 수를 이용(3~)
				if (i % j == 0) { // i가 j로 나누어떨어지면
					check++; // check!
				}
			}
			

			if (check % 2 == 0)  // check이홀수면 open
				dp[i]++;
			
		}
		return dp[number];
	}

}

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