[백준 15736] 청기백기 (자바)

백준 15736번: 청기백기 규칙 (2트)

문제 설명

청기와 백기를 N개 세워놓습니다. 처음에는 모든 깃발이 청기 상태입니다. 규칙에 따라 k번째 사람은 k의 배수 위치에 있는 깃발을 뒤집습니다. 이 과정을 1번부터 N번까지 반복합니다. 이 규칙을 따른 후 백기 상태로 남아있는 깃발의 수를 구하는 문제입니다.

문제 접근 방법

1. 깃발의 상태를 1번부터 N번까지 순차적으로 뒤집습니다.
2. 깃발의 상태가 변경되는 횟수는 해당 깃발의 약수의 개수와 같습니다.
3. 약수의 개수가 홀수인 경우에만 백기 상태로 남게 됩니다. 이는 약수의 개수가 홀수인 경우는 제곱수일 때만 발생합니다.
4. 따라서 1부터 N까지의 숫자 중 제곱수의 개수를 세면 됩니다.

시간 복잡도 분석

O(1)

이 문제는 단순히 N의 제곱근을 계산하여 정수 부분만 구하면 됩니다. 제곱수의 개수는 N의 제곱근에 해당하기 때문에 시간 복잡도는 O(1)입니다.

해결 방법

아래는 주어진 규칙을 만족하는 깃발의 개수를 계산하는 Java 코드입니다:

package re_02;

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

public class BOJ_15736_청기백기_규칙_2트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println((int) Math.sqrt(N));
    }
}