백준 13909번 [창문 닫기](C++) -yes6686- 티스토리

백준 문제 풀이: 13909 [창문 닫기]

---

문제 링크: https://www.acmicpc.net/problem/13909

문제 설명:

1번부터 n번까지 번호가 붙은 창문이 있습니다. 처음에는 모든 창문이 닫혀 있으며, 다음 규칙에 따라 창문을 여닫습니다:

1. 1번 사람은 모든 창문을 연다.
2. 2번 사람은 2의 배수에 해당하는 창문을 닫는다.
3. 3번 사람은 3의 배수에 해당하는 창문의 상태를 바꾼다(닫힌 창문을 열고, 열린 창문을 닫는다).

이 과정을 n번 사람까지 반복한 후에, 열린 창문의 개수를 출력하는 문제입니다.

특정 창문이 열린 상태로 남아 있으려면, 해당 번호의 약수 개수가 홀수여야 합니다. 약수의 개수가 홀수인 수는 완전제곱수뿐입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 창문의 개수
    cin >> n;

    int ans = 0; // 열린 창문의 개수
    int i = 1;

    // 완전제곱수 계산
    while (i * i <= n) {
        ans++; // i^2이 n 이하이면 열린 창문 하나 추가
        i++;
    }

    cout << ans << '\n'; // 결과 출력

    return 0;
}

예제 입력:

24

예제 출력:

4

---

코드 설명

• 핵심 알고리즘: 약수의 개수가 홀수인 수는 완전제곱수뿐이므로, n 이하의 완전제곱수를 계산하여 열린 창문의 개수를 구합니다.
• 구현 세부사항:
  • i * i가 n보다 작거나 같은 경우 ans를 증가시킵니다.
  • 반복문은 i가 1부터 시작하여 √n까지 순회합니다.
• 시간 복잡도: √n번 순회하므로 O(√n)입니다.

---

결과

입력된 창문의 개수 n에 대해 열린 창문의 수를 정확히 계산하여 출력합니다. 문제는 수학적 사고와 효율적인 반복문 구현을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!