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

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

15736번: 청기 백기

✅ 실버 Ⅳ

 

🔶 풀이

완전 탐색으로 풀면 범위가 너무 넓어서 시간 초과가 발생한다.

규칙을 찾아서 해결해줘야되는 문제.

 

1은 약수가 1개, 한 번 뒤집힘

2는 약수가 2개, 두 번 뒤집힘 = 그대로 청색

4는 약수가 3개, 세 번 뒤집힘

6은 약수가 4개, 네 번 뒤집힘 = 그대로 청색

9는 약수가 3개, 세 번 뒤집힘

 

루트 N이 정수일 때만 백기 상태로 뒤집히는 것을 알 수 있다.

따라서, N보다 작은 제곱수 개수를 찾아서 더 해주면 된다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int N = Integer.parseInt(br.readLine()); // 깃발 수
        int cnt = 1;
		
        for (int i=2; i<=N; i++) {
            if (i * i > N) {
                break;
            }
			
            cnt++;
        }
		
        System.out.println(cnt);
    }
}