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이 되므로 적절한 커팅이 필요하다.

1. 문제에서 제시한 규칙을 천천히 따라하면 어렵지 않게 풀 수 있다.

2.

1) 주어진 내용을 그대로 따라서 작성할 수 있다.먼저 하나의 문자열로 입력받는다.‘+’를 만날 때까지 문자열을 str1 문자열에 복사한다.‘=’를 만날 때까지 문자열을 str2 문자열에 복사한다.나머지 문자열을 str3 문자열에 복사한다.각 문자열을 strrev(문자열) 함수를 이용하여 뒤집는다.이제 뒤집힌 각각의 문자열을 숫자 n1, n2, n3 로 변환한다.if ( n1 + n2 == n3) 인 경우에는 True 를 그렇지 않은 경우에는 False 를 출력한다.

2) 문자열을 입력받고 뒤집는 작업 없이 바로 숫자로 작성할 수 있다.문자열의 처음부터 숫자로 변환하는 것이다. 가중치를 적절히 조정하면 된다.문자열이 str 에 저장되어 있고 문자열의 길이가 len 이라고 할 경우int deci = 1;int n1 = 0;for(int i = 0 ; i < len ; i++){ n1 = n1 + deci * (str[i] - '0'); deci = deci * 10;}과 같은 형식을 이용하면 된다.

3. 찾는 숫자는 0 에서 9까지 수중 하나이므로 한 자리 수이다. 따라서 주어진 숫자가 무엇이든 상관없이 우리는 0에서 9까지의 숫자를 이용하여 test 해봄으로써 문제를 해결할 수 있다. 각각의 숫자를 배열에 나누어 넣어서 해결하는 긴 자리 덧셈을 이용한다.

- 자리수가 50자리까지 이므로 문자열로 입력받는다.- 입력받은 문자열을 숫자 배열에 하나씩 나누어 넣는다.- 0 더해 보고 원하는 숫자가 포함되어 있는지 알아본다. 있다면 종료한다.- 0에서 종료되지 않았다면 1을 더해본다. 있다면 종료한다. 없다면 원래의 값을 가지고 다음 단계로 넘어간다. 단, 1이상의 숫자를 테스트 할 경우에는 자리 올림 할 경우가 있으므로 주의한다.

4. 앞에서부터 생각하는 것이 힘들다면 거꾸로 생각해보자.

① 주머니가 한 개 남아 있다면 차례가 온 사람은 모두 가져가므로 승자가 된다. 따라서 Alice 의 차례라면 Alice는 구슬이 몇 개 들어 있든 모두 가져가야 이길 수 있다.

② 주머니가 두 개 있다고 가정해 보자.첫 째 주머니에 구슬이 한 개, 두 번째 주머니에 구슬 1개 이상 인 경우에는 Alice가 이길 방법이 없다. 첫 째 주머니 구슬을 Alice 가 가지고 가면 ①의 경우가 되어 Bob이 나머지 구슬을 모두 가지고 갈 것이기 때문이다.

③ 그런데 첫 째 주머니에 구슬이 2개 이상인 경우에는 Alice가 이길 수 있다. 첫 째 주머니에 구슬을 한 개만 남겨 놓으면 되기 때문이다. Bob이 두 번째 주머니에 남은 한 개의 구슬을 가져 갈 수밖에 없으므로 ①의 경우가 되어 차례가 된 Alice가 마지막 주머니의 구슬을 모두 가져간다.

④ 주머니가 세 개 이상이 되면 생각할 것이 많아진다. 하지만 마지막 주머니를 Alice이 가지고 간다고 가정하고 거꾸로 계산하여 첫 주머니까지 도달 했을 때 Alice가 첫 주머니의 구슬을 가지고 갈 수 있다면 Alice가 이기는 것이고 그렇지 못하다면 Bob이 이기는 것으로 답을 구할 수 있다.

예를 들어보자. 7번 주머니의 구슬을 Alice가 가지고 간다고 가정한다. 따라서 역으로 생각하여 7번 주머니에서 1번 주머니까지 진행한다.

5. 이러한 문제의 경우

1) 문제의 제시 조건을 잘 파악하는 것이 중요하다.

2) 제시조건을 온전히 이해한 후에는 단순 반복문을 이용하여 시간제한이 허락하는 범위까지는 부분점수를 받을 수 있도록 하나의 프로그램을 작성해 놓는다.

3) 단순 반복문을 이용하여 여러 예들을 출력한 후에 규칙성을 찾아보려는 노력이 필요하다. 더구나 N 제한이 10억까지 이므로 단순히 N번을 반복한다면 시간 초과에 걸린다.

4) 단순 반복문을 이용한 출력 결과를 보면 재미있게도 토끼수들은 0, 1, 2, 3 만으로 구성되어 있다는 것을 알 수 있다.그 이유는 4이상의 수를 포함하게 되면 곱의 결과값이 곱에 못 미치기 때문이다.예를 들면 4 * 4 = 16 인데 결과 값 16의 각 자리 수를 더하면 7밖에 되지 않는다.5 * 5 = 25 인데 결과 값 25의 각 자리 수를 더하면 7밖에 되지 않는다.이후의 숫자는 더욱 차이가 벌어진다.

5) 따라서 우리는 배열을 큐로 이용하여 1, 2, 3으로 초기화 한 후에 이 수들을 10의 자리로 하여 만들어진 10, 11, 12, 13, 20, 21, 22, 23 ...의 수들이 토끼수가 되는지 확인하여 큐에 삽입한다. 이러한 식으로 10억까지 모든 수를 짧은 시간에 구할 수 있다.

6) 이렇게 구하여진 수들은 자연히 오름차순 정렬이 되어 있으므로 입력 받는 두수 사이의 개수를 구하는 일은 아주 쉬운 문제가 된다.