[P&B] #100 BAEKJOON 13909

공log/[P&B]

[P&B] #100 BAEKJOON 13909

ming_OoO 2023. 9. 30. 19:40

728x90

백준 13909번 창문 닫기 JAVA

문제 설명

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

나의 문제 풀이 코드

import java.io.*;

public class bj13909 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        long result = findOpenWindows(N);
        System.out.println(result);
    }

    private static long findOpenWindows(long num){

//        long openWindows = 0;
//        for (long i = 1; i <= Math.sqrt(num); i++) {
//            long sqrt = (long) Math.sqrt(i);
//            if (sqrt * sqrt == i) {
//                openWindows++;
//            }
//        }

        // 완전제곱수의 개수는 sqrt(num)의 정수 부분과 같습니다.
        long sqrtNum = (long) Math.sqrt(num);
        return sqrtNum;
    }
}

문제 풀이 코멘트

이 문제를 처음에 보고 소수를 구하듯 boolean 배열에 모든 값을 넣어서 그 배수들의 인덱스로 계산해야하나 생각했습니다. 하지만 아래와 같이 N이 10이라는 가정하에 직접 구현해보면 규칙이 보입니다.

1번째 사람 : 1111111111
2번째 사람 : 1010101010
3번째 사람 : 1000111000
4번째 사람 : 1001111100
5번째 사람 : 1001011101
6번째 사람 : 1001001101
7번째 사람 : 1001000101
8번째 사람 : 1001000001
9번째 사람 : 1001000011
10번째 사람 : 1001000010
10번째 사람까지 진행한 후 열려 있는 창문의 번호는 1번, 4번, 9번입니다. 이 수들의 공통점은 완전 제곱수라는 것입니다.

완전제곱수는 어떤 양의 정수를 제곱하여 얻을 수 있는 수를 의미합니다. 예를 들어, 1, 4, 9, 16, 25 등은 완전제곱수입니다. 이런 완전제곱수는 각각 1^2, 2^2, 3^2, 4^2, 5^2와 같이 어떤 정수를 제곱한 값으로 나타낼 수 있습니다.

즉, N까지의 완전 제곱수의 개수를 구하면 되는 문제였습니다.

처음에는 완전 제곱수를 다음과 같이 구했습니다.

    private static long findOpenWindows(long num){
        long openWindows = 0;
        for (long i = 1; i <= num; i++) {
            long sqrt = (long) Math.sqrt(i);
            if (sqrt * sqrt == i) {
                openWindows++;
            }
        }
        return openWindows;
    }

하지만 이 코드는 시간복잡도가 O(N)입니다. 그래서 이 코드를 더 최저화 할 수 있는 방법을 찾아보았습니다.

제곱근(√)은 어떤 수를 제곱해서 그 수를 얻을 때 사용하는 연산입니다. 따라서 어떤 수 num이 완전제곱수인지 확인하려면 해당 수의 제곱근을 구한 후, 그 결과가 정수인지 확인하면 됩니다. 만약 num이 완전제곱수라면, 제곱근의 결과는 정수일 것이고, 그렇지 않으면 제곱근의 결과는 소수점 이하를 가지는 실수일 것입니다.
따라서 sqrt(num)의 정수 부분을 구하면, num이 완전제곱수인 경우에는 그 값과 일치하게 되며, 완전제곱수가 아닌 경우에는 소수점 이하를 버리고 num과 다른 값을 가질 것입니다. 이것이 왜 완전제곱수의 개수를 sqrt(num)의 정수 부분과 같게 되는지에 대한 이유입니다.

다시말해, N까지의 완전 제곱수의 개수는 N의 제곱근 정수 부분과 같습니다. 그리고 그 코드는 다음과 같습니다.

private static long findOpenWindows(long num){
	long sqrtNum = (long) Math.sqrt(num);
    return sqrtNum;
}

이 코드는 더 간단하며 시간 복잡도가 O(1)입니다. 완전제곱수의 개수를 찾아서 반환하므로 입력값 N에 관계없이 빠르게 결과를 구할 수 있습니다.

실제 예시를 직접 구현해보고 그 속에서 규칙을 구해 최대한 시간 복잡도가 최적인 코드로 구현하면 통과할 수 있는 문제였습니다!

~~(우와 100번째 글이닿ㅎㅎㅎ)~~

728x90