11월 1주차 모의테스트 문제
1. 생성 불능 숫자
2. 숫자의 종류
3. 슈퍼스타 K
4. 인수분해
5. One Register

1번과 2은 for 만 돌려서 단순히 비교해도 값을 찾을 수 있다.

3. 슈퍼스타 K

fast-fast(FF),  fast-slow(FS),  slow-fast(SF),  slow-slow(SS)
네 가지 데이터가 공백으로 입력되며 아래와 같이 3가지 조건이 주어진다.
1) 최대한 많은 곡을 넣어야 한다.
2) 빠른 템포로 시작하는 곡(FF 혹은 FS)을 1곡 이상 작곡하였을 경우 이 중에서 하나로 앨범의 첫 번째 곡을 시작해야 한다. 만약 FF혹은 FS인 곡이 한곡도 없을 경우 아무것이나 시작되어도 된다.
3) 한 곡이 끝나고 다음 곡의 시작 템포는 마지막의 템포와 동일한 곡이어야 한다. 다시 말해 빠른 템포로 끝난 곡은 빠른 템포로 시작하는 곡만 올 수 있으며, 느린 템포로 끝나는 곡은 느린 템포로 시작되는 곡만 올 수 있다.

각각의 입력데이터가 0인 경우(0으로 표시)와 0이상인 경우(1로 표시)를 생각하며 아래와 같은 표를 만들어 보자.

입력 받을 때 배열로 입력받고
위 표에서와 같이 이진수로 바꾼 후에 다시 10진수로 변환하여
각각의 경우를 정의하면 된다.
번호 6의 경우는 함수로 정의한다면 좀 더 효율적이 될 것이다.

4.  인수분해

문제에서 요구하는 조건을 보자.
입력받는 수를 n이라고 할 때 n을 인수분해 할 수 있는 모든 경우의 수를 구하는 것이다.
인수분해 결과로 나온 수들의 곱에서 수들의 순서는 생각하지 않는다.
따라서 같은 수들로 구성된 곱의 결과물이 나오지 않아야 한다.
n의 범위가 20억이나 되어 생각을 힘들게 할 수도 있지만 일단 범위는 생각하지 말고 가장 간단한 수들로 몇 가지 예를 만들어 보자.

특징을 살펴보면
1) 소수인 수들은 개수가 0 이라는 것.
2) 합성수인 수들을 수의 곱으로 나타낼 때 뒤에 나오는 수는 앞에 나온 수보다 크거나 같다는 것이다. 12의 예를 보면 3*로 시작된 인수분해 결과에서 뒤에 나오는 수가 3보다 작은 수는 없다.

따라서 합성수가 어떤 수로 나누어지는 경우를 생각할 때 n의 제곱근 까지만 생각해보면 된다. 또한 n이 n의 제곱근 이하의수 수 x로 나누어지는 경우 나온 결과를 y라고 할 때
y의 경우도 n의 경우와 마찬가지로 생각할 수 있다. 이후도 마찬가지 재귀적으로 이루어지는 것을 알 수 있다.

따라서 깊이 우선탐색을 이용할 수 있으며  각각의 경우 주어진 수의 제곱근까지만 고려하므로 20억에 대한 고민은 하지 않아도 된다.

5. One Register

문제의 조건에 맞추어 몇 가지 수들을 test 해 보라.

입력받는 두 수를 N, M 이라고 할 경우 M에 초점을 맞추어 생각해 보자.

큐의 초기값으로 기본적인 값을 넣고 초기값에 대한 테스트를 한 후에 BFS를 진행한다.
진행시에 ‘-’와 ‘/’는 필요 없으므로 제외하고 ‘*’와 ‘+’만 가지고 한다.

진행되는 값이 int 범위를 초과할 수 있으므로 __int64 를 이용한다.
2번 큐의 값이 1인 경우 추가되는 rear 값의 곱셈의 결과는 언제나 1이 되므로 적절한 커팅이 필요하다.