사이냅소프트 2016 경력 공채 문제

우선 위의 문제에서 하나 말할 것은, 99일 때는 답이 01입니다. Wolframalpha 자료를 첨부합니다. 사이냅소프트에서 왜 10이라고 했는지는 저도 잘 모르겠습니다.

딱 나누어지는 경우는 출력하지 않고, 무한소수일 경우에만 반복되는 부분을 출력하며, 외부 라이브러리는 사용할 수 없습니다. 채용 분야에서 제시된 언어는 C++,Java,Javascript 등이 있으므로 여기서는 C++로 문제를 풀겠습니다. 사실 이러한 유형의 문제는 동적 프로그래밍을 연습해 볼 수 있는 좋은 문제라고 생각합니다. 나눗셈을 손으로 해본다 생각하면, 1/7의 경우 맨 처음 몫은 0, 그 다음 10을 곱하여 10이 됩니다. 그 다음의 몫은 1, 나머지는 3이므로 다음엔 30을 7로 나눠야 합니다.

이런식으로 어떤 단계에서 나눠야 될 수가 0이 아닐 때, 현재 나눠야 할 수가 2번 이상 나올 경우 그 수는 반복된다고 볼 수 있습니다. 따라서 먼저 반복되는 구간이 발견되었을 때부터, 나누는 과정을 그대로 출력해주면 됩니다.

#include<iostream>
using namespace std;

int main()
{
    for (int i = 1; i <= 100; i++)
    {
        bool f1[1001] = { false }, f2[1001] = { false }, endless = true;
        int a = 1;
        while (!f1[a])
        {
            if (a%i == 0)
            {
                endless = false;
                break;
            }
            f1[a] = true;
            a = (a % i) * 10;
        }
        if (!endless) continue;
        cout << i << " ";
        while (!f2[a])
        {
            f2[a] = true;
            cout << a / i;
            a = (a % i) * 10;
        }
        cout << "\n";
    }
}