<Algorithm> 208. 만취한 상범(BOJ)

1. 6359번 만취한 상범(BOJ)

   사용 알고리즘 :  DP

• 배수 규칙을 이용하는 기초 DP 문제, 다른사람 코드들도 방식만 다르고 같은 원리를 이용했다.

• i*j 는 i의 배수가 여러 부분에서 활용이 가능한 것 같다.

문제에 대한 접근&생각

1. 매라운드 마다 K번째 배수로 방문의 상태가 변함 -> DP! (i*j는 i배수) -> 마지막에 결과값이 누적!

코드 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        /***************************
         * i*j는 i의 배수가 되는 규칙을
         * 이용하여 모든 경우에 대해
         * 방이 열고 닫히는 것을 판단한다.
         * 즉 마지막 라운드에 결과가 누적된다. 
         ***************************/
        for(int t = 0; t < test; t++) {
            int n = sc.nextInt();
            int[] dp = new int[n+1];
            Arrays.fill(dp, 1);
            for(int i = 2; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(i*j <=n)
                        dp[i*j]*=-1;
                }
            }
            long count = Arrays.stream(dp).filter(i->i==1).count();
            System.out.println(count-1);
        }
    }
}