Joonas' Note

Joonas' Note

Google code jam - Qualification Round 2016 본문

알고리즘/문제 풀이

Google code jam - Qualification Round 2016

2017. 10. 29. 16:24 joonas

    [이전 블로그로부터 글 옮김]


    GCJ 링크 : https://code.google.com/codejam/contest/6254486/dashboard

    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를 사용)


    Problem D - Fractiles

    문제 이해 못함



    Comments