[java] 백준 13909 창문 닫기

n번째 사람이 n의 배수에 해당하는 창문을 닫혀있으면 열고, 열려있으면 닫는 문제이다.

 

이 문제는 메모리가 64mb로 제한적이고 입력값은 <21억이므로 입력값은 매우 크다.

 

즉 메모리 효율이 좋은 문제풀이가 요구된다. 

 

우선 메모리를 무시하고 풀어보자.

 

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());
        boolean window[] = new boolean[N];
        // 길이가 N인 boolean타입의 배열을 선언한다.
        // 배열은 기본적으로 false로 초기화 되어있다. false가 닫힘, true가 열림이다.
        
        int count = 0;
        // 열린 창문 수를 세는 메소드

        for (int k = 1; k < window.length + 1; k++) {
			//k번째 사람일 때 
            
            for (int i = window.length; i > 0; i--) {
                if (i % k == 0) {
                    window[i - 1] = !window[i - 1];
                    //i번째 창문이 k배수라면 boolean타입을 반대로 변경
                }

            }
     
        }
        for (boolean a : window) {
            if (a == true) {
                count++;
            }
            // 열린창문세기
        }

        System.out.print(count);
    }

}

 

이런식으로 boolean 특성을 이용하여 풀이를 할 수 있다. 

 

하지만 메모리를 신경써야한다, 즉 연산을 줄일 어떠한 규칙이 있을 것으로 생각할 수 있다.

 

그렇다면 수를 차례대로 넣으며 true가 나오는 배열의 값을 알아내 보자

 

N = 3    T F F

N = 4    T F F T 

N = 5    T F F T F 

N = 6    T F F T F F 

N = 7    T F F T F F F 

N = 8    T F F T F F F F 

N = 9    T F F T F F F F T

 

1, 4, 9번째 자리에 true가 반환되는 것을 알 수 있다. 즉 어떤 수의 제곱에 true를 반환하는 것이다.

 

즉  N보다 작은 수 중 1부터 시작하는 수들의 제곱값 개수를 구하면 된다.

 

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

        for (int i = 1; i * i <= N; i++) {
            count++;
        }

        System.out.print(count);
    }

}

 

이렇게 매우 간단한 코드로 해결할 수 있다.

 

시간과 메모리가 제한적이라면 규칙을 찾아보도록 하고, 겹치는 연산을 제거해보도록 하자.