13909번: 창문 닫기

 

- 관련 사이트: https://www.acmicpc.net/problem/13909

13909번: 창문 닫기

 

N개의 창문을 1번부터 N번의 사람이 본인 번호의 배수 번째 창문을 현재 상태 (열림, 닫힘)와 반대로 했을 때, 마지막에 열려있는 창문의 개수를 구하는 문제이다.

 

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

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

 

이를 직접 시뮬레이션을 해서 결과를 구해주면, 런타임 에러가 발생된다.

 

#include <iostream>
using namespace std;

void updateWindow(bool* window, int N, int n)
{
    for (int i = n; i <= N; i+=n)
        window[i] = !window[i];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, cnt;
    cin >> N;
    bool window[N+1];
    for (int i = 0; i <= N; i++)
        window[i] = true;
    
    for (int i = 2; i <= N; i++)
        updateWindow(window, N, i);
    
    cnt = 0;
    for (int i = 1; i <= N; i++)
        if (window[i])
            cnt++;
    cout << cnt << "\n";
    return 0;
}

 

따라서, 직접 구해주기 보다는 다른 방식으로 풀어주었다.

 

열려 있는 창문은 아래와 같이 홀수개의 약수를 가지고 있어야 한다.

9번째 창문: 1번째 사람, 열기 > 3번째 사람, 닫기 > 9번째 사람, 열기 → 열기

10번째 창문: 1번째 사람, 열기 > 2번째 사람, 닫기 > 5번째 사람, 열기 > 10번째 사람, 닫기 → 닫기

13번째 창문: 1번째 사람, 열기 > 13번째 사람, 닫기 → 닫기

24번째 창문: 1번째 사람, 열기 > 2번째 사람, 닫기 > 3번째 사람, 열기 > 4번째 사람, 닫기 > 6번째 사람, 열기 > 8번째 사람, 닫기 > 12번째 사람, 열기 > 24번째 사람, 닫기 → 닫기

 

일반적으로 한 수의 약수는 각각의 짝을 이루고 있으나, 제곱수의 경우 홀수개의 약수를 가지고 있다.

따라서, 제곱수의 개수를 구해주면 된다.

 

#include <iostream>
using namespace std;

int main()
{
    int N, cnt;
    cin >> N;
    cnt = 0;
    for (int i = 1; i * i <= N; i++)
        cnt++;
    cout << cnt;
    return 0;
}

- 메모리: 2020 KB

- 시간: 0 ms

- 코드 길이: 182 B