ACM 10110 Light, More Light

ACM - 10110
Programming Challenges - 110701

우리 학교의 어떤 복도는 전구마다 불을 켜고 끄는 스위치가 있다. 불이 꺼져 있을때 스위치를 누르면 불이 켜지고 다시 스위치를 누르면 불이 꺼진다. 처음에는 모든 전구가 꺼져 있다.

복도에 n개의 전구가 있을 때, 복도를 n번 왕복하면서 i 번째 갈 때 i 로 나누어 떨어지는 숫자의 위치에 있는 스위치를 누르고 돌아올 때는 누르지 않는다.

이런 식으로 스위치를 누를 때 n개의 전구가 있을 때 n번 왕복하며 스위치를 누를 때 가장 마지막 전구의 상태를 출력하는 프로그램을 작성하자.

입력
전구의 수를 나타내는 정수 (2^32 - 1 이하) 를 입력하고, 출력한다.

출력
전구가 켜져 있으면 "Y"를 꺼져 있다면 "N"를 출력한다.

입력 예제
3
6241
8191

출력 예제
N
Y
N

손쉽게 아래 알고리즘을 설계할 수 있다.
어차피 마지막 전구의 상태만 출력할 수 있으면 되므로, 다른 전구가 켜지든 말든 상관하지 않아도 된다.
따라서 1부터 N까지의 정수로 N을 하나씩 나누어 보면서
나누어 떨어지는 숫자가 나올 때 마다 bool값의 스위치값을 반대로 설정해 주고, 끝나면 스위치 값을 화면에 뿌려주면 된다...
하지만 속도를 개선해야 한다면? 일단 다음 소스를 보자...

#include <stdio.h>

char switch_light(int n)
{
bool onoff = false; //초기 전구값

for (int i=1; i<=n; i++)
{
if (n % i == 0) //마지막 전구만 알아내면 된다.
{//꺼져있으면 켜고, 켜져있으면 끈다.
if (onoff == false)
onoff = true;
else
onoff = false;
}
}

if (onoff == true) //마지막 전구값 리턴
return 'Y';
else
return 'N';
}


void main(void)
{
int n;
scanf("%d", &n);

printf("%c\n", switch_light(n));
}

사람이 생각하는 방식과 똑같이 구현된 알고리즘이다.
한번씩 지나가면서 마지막 전구만 켜고 끄게 설계되어 있다.
그렇지만 결과도출에 시간제한을 걸어 버린다면, for문으로 해결할 수 없게된다.

그럼 처음으로 돌아가서 문제를 다시 확인 해 보자.
N을 켜고 끄려면 N만큼 i의 회수를 증가하면서 켜고 끄는동작을 반복한다. 즉 1 <= i <= N 이라는 결과가 성립하게 되는데.
나누어서 떨어지는 숫자라는 것은. 약수를 말한다. 다른 모든 약수를 제외하면 그 어떤 정수이건 간에 1과 자기 자신은 약수로 가지게 된다.
그렇다면 첫번째 지나갈때와 N번째 지나갈때는 무조건 한번씩 켜고, 끄게 되므로 최종적으로는 꺼져 있게 된다. 결국 변화가 없다는 이야기다.

문제를 조금 더 좁혀 보면, 1과 자기자신을 제외하고 약수가 없다면(정수의 범위 내에서) 이 전구는 결국 꺼져 있게 된다.
그럼 약수를 구해야 할까? 아니다. 조금 더 문제를 좁혀 보자.

9의 제곱근은 -3과 3이다. 즉 -3과 3을 제곱하면 9가 된다는 소리다.
여기서 1과 N사이의 범위에 포함되는 것은 3 하나 뿐이다.
9의 약수는 (1, 3, 9) 3개가 존재한다. 좀 전에 말했듯이 1과 자기자신을 제외하면 3이 남는다.
이것이 무슨말인고 하니, 정수의 제곱근을 가지는 정수 N의 약수는 홀수라는 소리다. 즉 불이 켜진다.
정수를 제곱근으로 가지지 않는 N을 하나 예를 들어보자.
약수를 순서대로 나열하면, 제곱근을 가운데로 두고 양쪽에 짝수개의 약수가 배열된다.
정리를 하자면, 양수의 정수를 제곱근으로 가지는 정수 N이 있다면, N의 약수는 홀수개 이다.
11, 8, 13 과 같이 정수를 제곱근으로 가지지 않는 정수는 1과 자기자신을 제외한 약수가 없거나, 있다해도 제곱근이 없으므로 짝수가 된다. 즉 불이 꺼진다.

즉, N을 입력받아 양의 제곱근이 있는지 판단하여, 있다면 전구가 켜져있는 것이고, 아니라면 꺼진 것이다.

#include <stdio.h>
#include <math.h>

int main()
{
long unsigned double cN=0, cTrue = 0;

while (1)
{
scanf("%Lf",&cN);

if ( cN == 0 )
return 0;

cTrue = sqrt(cN); //제곱근 구하기

if ( cTrue * cTrue != cN ) //다시 제곱하여 그 숫자와 일치하는지
printf("N\n");
else
printf("Y\n");
}
}