백준 13909번 : 창문 닫기 (C 언어)

https://www.acmicpc.net/problem/13909

13909번: 창문 닫기

Code:

#include <stdio.h>
 
int main(void)
{
    int n;
    int count = 0;
    scanf("%d", &n);
    for (int i = 1; i * i <= n; i++)
    {
        count++;
    }
    printf("%d", count);
}

문제풀이:

단순하게 시간초과 등 조건이 없으면 구할수는 있는 문제이다.

하지만 쉽게 생각해 보면 마지막에 열려 있기 위해서는 홀수번을 해야 열린상태로 남겨지게 된다.

각 수의 약수 만큼을 열었다 닫았다 하므로 홀수개의 약수가 있는 것은 제곱수들만 남게 된다.

이 제곱수의 개수를 체크하면 문제가 쉽게 해결된다.