오늘의 코드. 7일차 (백준/13909번 창문 닫기)

해당 문제와 비슷한 내용을 수학퀴즈 관련된 도서에서 본 기억이 나서 문제를 풀어보게 되었다.

 

Baekjoon / Problem No. 13909  (창문 닫기)

 

Problem

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

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

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

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

Input

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

Output

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

---

Solution 

익히 봐와서 알겠지만, 조건을 보면 N의 범위는 무려 21억.

 

문제를 처음에 보면 "아, 그냥 반복문 몇개 돌려서 배열이나 벡터에다가 일일히 창문을 저장하여 직접 열고 닫기를 반복하면 되지" 라고 생각한다면, 백준은 '시간 초과'라는 문구와 함께 당신의 코드와 들여온 시간에 뒤통수를 때릴 것이다.

 

만약에 시간복잡도가 O(N^2)이나 O(N)과 같은 어설픈 알고리즘으로 통과하기에는 시간제한에 반드시 걸리게 된다. 

이 문제의 해답 방법은 다음과 같이 몇가지로 추려볼 수 있다.

 

1. '직접' 문을 여닫듯이 배열에 넣고 하나하나 실행 시킨다. (최소 21억번 넘게 열고 닫는다면 창문이 남아나질 않을것이다. 적어도 그 문이 일반적인 창문이라면.)
2. 조금 더 나아가 배열이나 벡터를 사용하지 않고 비트마스크 같은 방법을 사용하여 시간을 단축한다.
3. 열심히 생각해본다. 

열심히 생각해보자. 이 문제 조건에는 규칙이 있다.

	1번 문	2번 문	3번 문	4번 문	5번 문	6번 문	7번 문	8번 문
N=1	1	1	1	1	1	1	1	1
N=2	1	0	1	0	1	0	1	0
N=3	1	0	0	0	1	1	1	0
N=4	1	0	0	1	1	1	1	1
N=5	1	0	0	1	0	1	1	1
N=6	1	0	0	1	0	0	1	1
N=7	1	0	0	1	0	0	0	1
N=8	1	0	0	1	0	0	0	0

 

이후로도 계속 이어 나갈때, 결국 마지막에 열려있는 창문의 번호를 써보면 다음과 같다.

1번, 4번, 9번, 16번, 25번 ···

 

눈치 챘겠지만, 이 수들의 특징은 '완전 제곱수'이다.

또한, 제곱수의 특징은 약수를 '홀수개' 가진다. (EX. 4라는 제곱수가 있을때,√4 = 2 가 약수로써 2번 중복되기 때문에 약수는 {1,2,4} 로 홀수가 된다.)

 

자세한 내용은 여기에 정리되어 있다. : https://namu.wiki/w/%EC%A0%9C%EA%B3%B1%EC%88%98

 

그리고 이러한 제곱수의 특징은 

라는것. 여기서 √N을 감싼 기호는 가우스 기호로, "N보다 크지않은 최대 정수" 를 뜻한다. 

 

결국 코드는 N에 제곱근을 씌운 뒤, 수학에서의 버림(코드에서는 int로 만들어 주면 자동으로 버림이 된다.)을 진행해주는 코드를 짜면 되겠다.

---

Code

#include <cstdio>
#include <math.h>

int main()
{
    int N;
    scanf("%d", &N);
    printf("%d", (int)sqrt(N));
}

 

---

Review

분명 문제 하나를 푸는 데 소스코드 길이를 보니 문제를 푼것같지 않은 이 느낌, 뭔가 불쾌하달까.

 

2024년 2월 10일은 명절인 "설"입니다. 이 글을 보시는 여러분, 새해 복 많이 받으세요.