Silver 5 난이도 문제를 C++로 풀이한 내용입니다. N개의 창문이 있을 때, 특정 규칙에 따라 창문을 토글할 때 최종적으로 열려있는 창문의 개수를 구하는 문제입니다.

백준 13909: 창문 닫기

문제 소개

문제 번호: 13909
문제명: 창문 닫기
난이도: Silver 5
사용 언어: C++
실행 시간: 0 ms
메모리: 2032 KB

N개의 창문이 있고, 처음에는 모두 닫혀 있습니다. 1번부터 N번까지 창문이 있으며, 1부터 N까지의 각 숫자 i에 대해, i의 배수인 창문들을 토글합니다 (열려있으면 닫고, 닫혀있으면 엽니다). 최종적으로 열려있는 창문의 개수를 구해야 합니다.

접근 방법

문제를 이해하는 과정에서 각 창문이 몇 번 토글되는지 파악하는 것이 중요했습니다. 창문 k는 1부터 N까지의 숫자 i 중에서 i가 k의 약수인 경우에만 토글됩니다. 즉, 창문 k가 최종적으로 열려있으려면, k의 약수 개수가 홀수여야 합니다.

약수는 보통 쌍으로 존재합니다. 예를 들어, 12의 약수는 (1, 12), (2, 6), (3, 4)로, 쌍으로 존재하기 때문에 약수의 개수가 짝수입니다. 약수의 개수가 홀수가 되는 경우는 자기 자신과 쌍이 되는 경우뿐입니다. 예를 들어, 9의 약수는 (1, 9), (3, 3)으로, 3은 자기 자신과 쌍을 이룹니다. 이 경우 약수의 개수는 3개로 홀수입니다.

자기 자신과 쌍을 이루는 경우는 어떤 수 k에 대해 k * k = n 꼴일 때입니다. 즉, k = sqrt(n)이 정수일 때, n은 완전제곱수이며 약수의 개수가 홀수입니다. 따라서 최종적으로 열려있는 창문은 N 이하의 완전제곱수들입니다.

N 이하의 완전제곱수의 개수를 구하는 것은 1^2, 2^2, 3^2, ..., k^2 <= N을 만족하는 k의 개수를 세는 것과 같습니다. 이는 k <= sqrt(N)을 만족하는 k의 개수와 같으며, k는 1부터 시작하므로 floor(sqrt(N))이 됩니다.

풀이 과정

입력으로 N을 받습니다.
N 이하의 완전제곱수의 개수를 구합니다.
완전제곱수의 개수는 floor(sqrt(N))과 같습니다.
계산된 값을 출력합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin >> n;
    // 창문 k번은 k의 약수 개수만큼 토글됨
    // 약수는 보통 쌍으로 존재 (ex. 12 = (1,12),(2,6),(3,4)) → 짝수개 → 닫힘
    // 단, 자기 자신과 쌍이 되는 경우 (ex. 9 = (1,9),(3,3)) → 3이 혼자 카운트 → 홀수개
    // 자기 자신과 쌍이 되려면 k×k = n 꼴이어야 함 → k = √n 이 정수여야 함 → 완전제곱수만 약수 홀수개
    // 홀수번 토글 = 열림 → 완전제곱수만 열림
    // N이하 완전제곱수 개수: 1²,2²,...,k² ≤ N → k ≤ √N → k는 1부터 √N까지 → 개수 = √N
    cout << (long long)sqrt((double)n);
}

#include<bits/stdc++.h>: 표준 라이브러리의 대부분을 포함합니다.
using namespace std;: std 네임스페이스를 사용합니다.
int main(): 프로그램의 시작점입니다.
long long n;: 입력받을 N을 저장할 변수입니다. long long을 사용하여 큰 입력값도 처리할 수 있도록 합니다.
cin >> n;: N을 입력받습니다.
cout << (long long)sqrt((double)n);: N의 제곱근을 계산하여 정수 부분만 출력합니다. sqrt 함수는 double형을 반환하므로, (double)n으로 캐스팅하고, 결과를 long long으로 다시 캐스팅하여 정수 값을 얻습니다.

복잡도 분석

시간 복잡도: O(1). sqrt 함수는 상수 시간에 가깝게 실행됩니다.
공간 복잡도: O(1). 추가적인 공간을 사용하지 않습니다.

배운 점

이 문제는 약수의 개수와 완전제곱수 간의 관계를 파악하는 것이 핵심이었습니다. 복잡한 시뮬레이션이나 반복적인 탐색 없이, 수학적 성질을 이용하면 효율적으로 문제를 해결할 수 있음을 배웠습니다. sqrt 함수를 이용하여 완전제곱수의 개수를 직접적으로 구하는 방법을 알게 되었습니다.