[백준/Java] #13909 창문 닫기 - 메모리 초과 해결

 

 

문제

 

 

 

코드

 

처음에 작성한 코드는 문제에서 말한 그대로 풀이를 한 방식이었는데, 숫자가 커지니 메모리 초과가 발생했다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(br.readLine());
boolean[] arr = new boolean[N];

for (int i = 1; i <= N; i++) {
    for (int j = 0; j < N; j++) {
        if ((j + 1) % i == 0) {
            arr[j] = !arr[j];
        }
    }
}

int count = 0;
for (boolean b : arr) {
    if (b) count++;
}

bw.write(String.valueOf(count));
bw.close();

 

 

다른 방법으로 풀어야겠다 싶어서 규칙을 찾아보니

주어진 수 N이 정수 a의 제곱보다 크거나 같고 a+1의 제곱보다 작을 때 열려있는 창문의 개수가 a개인 것을 발견했다.

N		열린 창문의 수(count)

1		1 (1: 1의 제곱)
2		1
3		1

4		2 (4: 2의 제곱)
5		2
6		2
7		2
8		2

9		3 (9: 3의 제곱)
10		3
11		3
12		3
13		3
14		3
15		3

16		4 (16: 4의 제곱)
...

 

 

이대로 작성한 코드는 아래와 같다.

1부터 값을 증가시키고 조건에 부합하면 반복문을 종료한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(br.readLine());
int count = 1;

while (true) {
    if (Math.pow(count, 2) <= N && N < Math.pow(count + 1, 2)) break;
    else count++;
}

bw.write(String.valueOf(count));
bw.close();

 

 

정답이긴 했지만 반복문을 사용하지 않는 좀 더 직관적인 방법은 없을까 생각해 봤다.

N의 제곱근을 구하고 소수점 이하를 버리면 count가 나오는 것이 보였다.

 

최종적으로 코드가 아주 심플해졌다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int N = Integer.parseInt(br.readLine());
bw.write(String.valueOf((int) Math.sqrt(N)));

bw.close();

 

 

 

 

위쪽의 제출이 제곱근을 이용한 마지막 코드이고, 아래가 두번째 코드이다.

시간과 메모리로는 큰 차이가 나지 않는다.

 

 

꽤나 많은 문제들이 이런 식으로 규칙을 발견하면 간단히 해결되는 것 같다.