Google code jam - Qualification Round 2016 풀이
Problem A - Counting Sheep
N이 주어지면 N, 2N, ..., kN까지 진행했을 때, 0~9을 모두 사용하게 되는 시점 k에서의 kN을 구하는 문제이다.문제 그대로 시뮬레이션하면 된다. large set에서 범위가 $0 \le N \le 10^6$ 이지만 0~9가 모두 나오게 되는건 최대 100배이므로 int 범위로 충분히 표현할 수 있다.
Problem B - Revenge of the Pancakes
앞에서부터 k번째까지를 뒤집을 수 있다. (0~k 를 k~0으로 뒤집고 모든 -를 +로 뒤집는다. +-- 를 전부 뒤집는다면 ++- 이 된다.) 최소 몇 번을 이런 식으로 뒤집으면 +로만 이루어진 문자열을 만들 수 있을까?small set은 재귀로 구현했으나 코딩이 미숙하여 계속 틀렸다. 각 문자열을 1, 2, ..., n번까지 뒤집으면서 BFS를 진행하였다. small set은 길이 $S \le 10$ 이므로 모든 경우의 수는 $2^S$ 라서 최대 1024개만 탐색할 것이다.
small set의 정답을 들여다보고 large set을 해결할 수 있었다. 다음 문자열들은 모두 같은 연산 횟수를 가진다.
++---그러면 문제를 분할할 수 있다. 위 2개의 합은 세번째의 결과와 같다.
+++--
+--
+-
+++-
+++---연속되어 있는 문자열은 하나로 생각해도 무방하다. (뒤집는 과정을 생각하면 연속되어 있는 것은 한번에 뒤집는 것이 좋다는 걸 알 수 있다.) 그렇다면 -+ 또는 +- 들만 계산하면 된다.
+--
+++---+--
- 로 시작하는 경우는 처음에 등장한 - 를 뒤집고 나머지를 계산하면 된다.
Problem C - Coin Jam (small)
2진수의 길이가 N인 1~~~1의 형태(~는 0 또는 1)를 가진 10진수를 2, 3, ..., 10진수로 해석한 모든 수가 소수가 아닌 것들을 J개 출력하는 문제이다.small set은 단순 시뮬레이션으로 해결했다.
N=16, J=50인 경우의 결과를 보면 답이 3 2 5 2 7 2 3 2 11가 자주 등장하는 데, 각 진수들이 3 2 5 2 7 2 3 2 11로 나뉘는 경우들을 출력하면 large set(N=32, J=500)도 해결된다고 한다. (Big-Integer를 사용)
