[Java] 백준 15736번 : 청기 백기

문제

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

 

 

접근 방법

1. 청기가 위로 백기가 아래로 있을 때 1번학생은 1번 배수의 깃발을 뒤집고, 2번학생은 2번 배수의 깃발을 뒤집고, 3번은 3의 배수를 뒤집는 방식을 진행된다.
2. 맨처음에 어떤깃발이 청기고 어떤 깃발이 백기로 되어있는지 알 수 없어서 헷갈렸지만 밑에 힌트에 맨처음에 다 백기에서 시작된다고 나와있어서 보고 참고했다.
3. 1부터 24까지 규칙을 찾아보니 1, 4, 9, 16번의 깃발이 백기인것을 확인했다. N학생의 제곱수가 있으면 그것의 약수는 무조건 홀수이므로 답을 구한다. 완탐방식으로 하면 21억개 이므로 시간 초과가 발생한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader br;
    private static long N;
    private static int ans = 1;
    
    
    //입력
    public static void input() throws Exception{
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
    }
    
    //실행
    public static void process() {
        for(int i = 2 ; i * i <= N ; i++){
            ans++;
        }

        System.out.println(ans);
    }


    public static void main(String[] args) throws Exception{
        input();
        process();
    }
}