백준 15736 자바 청기 백기 (72ms 가장 빠른 코드!)

 

배수마다 깃발을 뒤집는 구조

1은 약수가 1개, 한번 뒤집힌다.

2는 약수가 2개 두번 뒤집힌다.    -> 두 번 뒤집히면 원래 그대로 청색

4는 약수가 3개, 세 번 뒤집힌다.

5는 약수가 2개, 두 번 뒤집힌다.

6은 약수가 4개, 4 번 뒤집힌다.

...

9는 약수가 3개, 세 번 뒤집힌다.

 

규칙을 발견하셨나요??

 

루트 N 이 정수 일때 약수가 홀 수로 나오게 됩니다.!

(= 약수의 제곱이 N일 때!)

 

만약에 N이 24라면 백기가 위로 올라오는 수는?

1, 4, 9, 16 입니다.

모두 루트를 해보면 1,2,3,4 입니다.

 

반대로 생각해보면 N보다 작은 제곱수를 찾으면 됩니다.

그렇다면 아래와 같이 제곱이 N보다 커지기 전까지 count를 해주면 나오게 됩니다!

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int count = 1;

        for(int i = 2; i <= N; i++){

            if(i * i > N){
                break;
            }
            count++;
        }

        System.out.println(count);

    }
}