Google Kickstart 2021 Round C

소스 코드 위치: Google Kickstart 2021 Round C solutions

 

A. Smaller Strings

  1. 주어진 문자열(s)의 넘어가지 않도록 첫 문자부터 건설해나가자. 문자 'a'부터 시작해서 문자 'a'+K-1까지 사용한다. 

  2. i(단, 0<= i <= ceil(N/2)-1)번째 문자가 s[i]보다 작다면 나머지 부분은 아무렇게나 구성해도 주어진 문자보다 사전적으로 작을 수 밖에 없다. 따라서 i번째 위치를 제외한 나머지 부분은 K^(ceil(N/2.)-1-i) 경우의 수가 발생한다.

  3. i번째 문자가 s[i]와 같다면 i를 증가하고 2.로 돌아간다.

 

  팰린드롬의 prefix를 결정하면 나머지 뒷 부분은 결정된다. 단, 길이가 홀수인 경우를 고려하여 따로 예외처리해줘야 한다.

 

B. Alien Generator

  특정 일수를 상수 d로 두자. 그러면 데이터가 K, K+1, ..., K+d-1로 표현된다. 이들의 합이 G와 같아야 하므로 아래 수식으로 정리할 수 있다.

G = K + (K+1) + ... + (K+d-1) = (K - 1 + 1) + (K - 1 + 2) + ... + (K - 1 + d) = (K-1)*d + d(d+1)/2

  K는 d가 정해지면 구할 수 있다. 따라서 브루트포스로 d=1부터 G보다 작거나 같을 때까지 반복문을 돌면서 (K-1)이 0보다 클 수 있는 정수인지를 검사하여 답을 도출하면 된다.

 

C. Rock Paper Scissors

  1. 매번 날에 새로운 게임을 진행할 때 이전 날의 기록을 사용하지 않는다. -> 각 날에 게임을 진행하는 것은 독립적이다.

  2. i번째 날에 j번째 라운드에서는 j-1번째 라운드까지의 데이터를 사용한다. 순서는 상관없이 rock, scissor, paper를 몇 번 냈는지만을 본다. -> 최적 부분 구조, 겹치는 부분 문제 -> 다이나믹 프로그래밍

 

  1.에서 각 날은 독립적이고, 문제에서 주어진 조건에선 어떤 X가 주어지든 답은 반드시 존재하므로 각 날마다 점수의 기대값을 최대로하면 반드시 X보다 크거나 같은 값이 나온다. 따라서 2. 구조를 파악하여 동적 프로그래밍을 구성한다.

dp[i][j][k] = i번 rock을 냈었고, j번 scissor를 냈었고, k번 paper을 낸 상태에서 가질 수 있는 점수의 기대값의 최대값

 

D. Binary Operator

  어휴 토나오는 구현 문제였습니다. 너무 어렵네요.

 

  1. arithmetic tree를 구성한다. 괄호 기준으로 트리를 만들고 자식을 가지는 노드는 연산자로 둔다. 이러면 중위 수식 표기를 트리로 나타낼 수 있다.

  2. 이제 트리를 순회하면서 데이터를 정리한다. 먼저 수에 대해서는 곱셈이나 덧셈은 바로 계산되므로 처리한다. 단 여기서 정의되는 토탈 펑션(#)을 처리하기 위해서 다음과 같은 자료구조가 필요하다.

1. 곱셈의 결과를 정의할 수 없는 경우엔 여기에 포함되는 요소를 리스트할 수 있어야 한다. 리스트에 포함된 요소는 모두 곱셈으로 표현되어야 한다. 추가적으로 계수도 표현할 수 있어야 한다. ex) ((1#2)*(1#3))*(3#3) -> list = ["1#2", "1#3", "3#3"], 계수=1 2. 1.에서 정의된 곱셈 리스트들을 덧셈으로 표현되어야 한다. ex) (((1#2)*(1#3)) + 2)*(3#3) -> (list1 = ["1#2", "1#3", "3#3"], 계수=1)  , (list2 = ["3#3"], 계수=2)

  3. 위처럼 정의된 자료구조를 토대로 주어진 표현식을 정리하고, 마지막에는 곱셈 리스트들을 일정한 규칙1로 정렬, 그리고 이들을 덧셈으로 표현하기 전에 일정한 규칙2로 정렬한 뒤 문자열로 정리한다. 일정한 규칙1, 일정한 규칙2는 구성 요소의 사전순으로 정렬하는 게 가장 간단하다.