[백준] java 13909 창문 닫기

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

문제

서강대학교 컴퓨터공학과 실습실 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)이 주어진다.

풀이 과정

문제를 접하자마자 굉장히 당황했다. 시간 제한이 1초인데 입력 범위가 21억이란다. 보통 O(N)이 1초가 걸리니 해당 문제를 O(N)으로 풀게된다면 약 21초가 걸린다는 이야기이다.

어떻게 풀지..? 일단 떠오르는 풀이를 작성하고 제출하였다.

떠오른 풀이는 다음과 같다. 먼저, 열린 문 숫자라는 뜻인 count 변수에 N을 저장하고 i부터 N까지 i에 대하여 나누어떨어지는 j가 있을 경우 해당 루프에서 isOpen 변수에 !isOpen을 저장한다. 결국 i번째 순회에서 isOpen이 false라면 닫혀있는 문이라는 뜻이므로 count를 1빼준다.

import java.io.*;

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 = N;

        for( int i = 2; i <= N; i++ ){
            boolean isOpen = true;
            boolean isPrime = true;
            for( int j = 2; j <= i; j++){

                if( i % j == 0 ){
                    isOpen = !isOpen;
                    isPrime = false;
                }
                else if( j*j >= i && isPrime) {
                    isOpen = false;
                    break;
                }

            }
            if( !isOpen )
                count--;

        }
        System.out.println(count);
    }
}

결과는 원하는대로 잘 출력된다. 하지만 문제는 제한 시간이다. 바로 시간초과에 걸려버린다.

1억번 안쪽으로 수행할 수 있는 로직이 뭐가있지..? 장장 4시간 정도를 고민한 것 같다..

도저히 답이 안나와 힌트를 얻고자 질문게시판에 들어갔다.

어떤 성질을 발견할 수 있다고한다..? (뭐가됐든 감사합니다 herdson님)

1부터 16까지 한 수가 갖는 모든 배수를 메모장에 나열했다.

규칙을 발견했다. 대부분 수의 배수 합이 짝수인데, 1, 4, 9, 16는 홀수이다. 그리고 1을 제외한 4, 9, 16은 모두 한 수의 제곱으로 표현할 수 있다. 예를 들어 4는 2², 9는 3², 16은 4²이다.

그렇게 질문게시판의 도움을 얻어 문제를 해결할 수 있었다.. 다음은 마지막에 제출한 자바 코드이다.

import java.io.*;

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*i <= N; i++ )
            count++;

        System.out.println( count );
    }
}

나가는 글

이렇게 약수, 배수와 소수2 카테고리를 끝냈다. 이제 본격적으로 여러 자료구조를 활용하여 푸는 카테고리인 것 같다.