[ 구글 코드잼 예선 ] Google Code Jam 2022 Qualification Round 리뷰

구글 코드잼 예선 Google Code Jam 2022 Qualification Round 리뷰

 

 

 

요즘 바쁘긴 하지만 코드잼은 빼먹을 수 없었다.

과거 작년 , 재작년 코드잼을 신청해놓고 그냥 놀아버려 도전도 하지 못했던 과거를 생각해 이번에는 신청한 김에 꼭 참여해보기로 했다.

 

Atcoder도 가끔 하고 , 백준도 요즘 건드리지 않고 있는데 머리에 알고리즘 불씨를 살려주기에 정기적인 공부만 한 게 없다. 가벼운 마음으로 공부한다 생각하고 도전해보았다.

 

구글 코드잼은 예선 통과만 하려면 30점 이상만 하면 되는 걸로 기억한다.  아마 앞의 3문제 A, B, C 문제만 맞혀도 자동 예선 통과로 알고 있다.

 

다음 라운드의 경우는 시험기간이라 도전하지 않을 생각이다. 어차피 그 이상의 의미있는 대단한 성적을 내는 것도 불가능할 듯하고 그래도 기록을 남기는 것은 언제나 좋다고 생각하기에 문제의 대략적인 리뷰를 블로그에 남겨놓기로 했다.

문제 풀이는 파이썬으로 진행하였다.

 

 

 

A. Punched Cards

Atcoder도 그렇고 백준 영어 문제도 그렇고 , 읽는 것부터 문제다.

뭐라 뭐라 막 써져 있는데 해석하는 부분에서 하나 삐끗해서 해석하면 완전 다른 문제가 된다.

아무튼 이건 이 문제에 대한 건 아니고 그냥 영어로 된 문제를 풀다 보니 느끼는 점이다...

 

문제는 펀치 카드를 그려내는 문제인데 , 문자열을 다루는 문제다.

좌측 상단 구석에 펀치 카드 , 즉 구멍이 난 상태로 r * c 크기의 펀치카드를 출력하면 되는 문제이다.

문자열을 다룰 줄 안다면 쉽게 풀 수 있는 문제다.

 

정답 제출 코드

#1
import sys
n = int(sys.stdin.readline()) + 1

def pline(level,c):
    if level == 1:
        print(".."+"+-"*(c-1)+"+")
    elif level == 2:
        print(".."+"|."*(c-1)+"|")
    elif level % 2 == 1:
        print("+-"*c+"+")
    elif level % 2 == 0:
        print("|."*c + "|")


for i in range(1,n):
    r,c = map(int, sys.stdin.readline().split(" "))
    print("Case #%d:" %i)
    for k in range(1,2*r+2):
        pline(k,c)

 

 

 

 

B. 3D Printing

이 문제도 해석이 안돼서 문제 해석에 공을 많이 들인 문제다.

영어 공부의 필요성을 많이 느끼게 된다.

 

아무튼 문제 내용은 3대의 프린터기에 사용할 수 있는 4가지 색들의 양이 정해져 있다.

이 4가지 색들의 잉크 양을 정하여 특정 색을 만들 수 있다. 그럴 때 , 다음 조건을 만족해야 한다.

 

1. 모든 프린터에서 해당 색상을 출력할 수 있어야 한다.

2. 해당 색상을 구성하는 물감의 양은 꼭 10**6 이어야 한다.

 

3가지 프린터기에 대해서 모든 프린터에 대해 인쇄가 가능하다면 , 그 가능한 경우를 출력하고 아니라면 불가능을 출력하는 문제다. 답이 여러 개라면 그중 맞는 답 한 가지만 출력한다.

 

예시)

300000 200000 300000 500000 

300000 200000 500000 300000 

300000 500000 300000 200000

 

이 경우 , 만드는 색은 300000 200000 300000 200000 빼고는 불가능하므로 , 300000 200000 300000 200000을 출력해야 한다.

 

알고리즘은 모든 프린터들 안에서 해당 색에 대해 최솟값을 찾아주고 4개의 색들의 최솟값들을 모두 더했을 때 , 10**6 보다 작다면 불가능 , 크다면 모두 최솟값으로 구성해주고 그 값들에서 10**6을 초과한 만큼 빼주어 딱 맞춰주면 된다.

 

정답 제출 코드

#2
import sys
n = int(sys.stdin.readline()) + 1

for i in range(1,n):
    c = []
    for _ in range(3):
        c.append(list(map(int , sys.stdin.readline().split(" "))))
    ac = min(c[0][0],c[1][0],c[2][0])
    bc = min(c[0][1], c[1][1], c[2][1])
    cc = min(c[0][2], c[1][2], c[2][2])
    dc = min(c[0][3], c[1][3], c[2][3])
    if ac + bc + cc + dc < 10**6:
        print("Case #%d: IMPOSSIBLE" %i)
    else:
        l = [ac,bc,cc,dc]
        check = ac + bc + cc + dc - 10**6
        for k in range(0,len(l)):
            if l[k] >= check:
                l[k] -= check
                break
            else:
                check -= l[k]
                l[k] = 0
        print("Case #%d: %d %d %d %d" %(i,l[0],l[1],l[2],l[3]))

 

 

 

C. d1000000

1부터 n까지 면을 한 개씩 가지고 있는 주사위들이 있을 때 , 이 주사위들을 배열하면서 1부터 1씩 증가하는 수열을 최대한 얼마나 길게 만들 수 있는 문제이다. 

 

단순하게 생각하면 오름차순으로 나열하고 , 그냥 가능한 부분에 대해서 넣어주면 된다.

즉 3이라는 숫자가 들어가야 하는데 1 ~ 6까지 수가 있는 주사위를 사용하기보다 1 ~ 4까지 있는 주사위를 활용하는 게 좋다는 것이다.

왜냐하면 1 ~ 6까지 주사위는 나중에 6이나 5 같은 수가 필요할 때 쓸 수 있기 때문이다.

이렇게 생각하면 그리디 스타일의 문제라고도 생각할 수 있을 듯하다.

 

예시 ) 3 3 5 1 7 4 3 주사위가 주어졌다.

정렬 : 1 3 3 3 4 5 7

주사위 1 => 1로 사용 / 주사위 3 => 2가 존재하는 주사위니까 2로 사용 / 주사위 3 => 3으로 사용

주사위 3 => 4로 써야 하는데 쓸 수 없으므로 넘김 / 주사위 4 => 4로 사용 / 주사위 5 => 5로 사용 

주사위 7 => 6을 포함하므로 6으로 사용

 

정답 : 1-1 3-2 3-3 4-4 5-5 7-6 => 최대 길이 6

 

정답 제출 코드

#3
import sys
n = int(sys.stdin.readline()) + 1

for i in range(1,n):
    k = int(sys.stdin.readline())
    dice = list(map(int,sys.stdin.readline().split(" ")))
    dice.sort()
    ans = 0
    level = 1
    for idx in range(0,len(dice)):
        if dice[idx] >= level:
            ans += 1
            level += 1
    print("Case #%d: %d" %(i,ans))

 

 

 

D. Chain Reactions

트리 구조처럼 기계들이 배치되어 있고 , 기계 들에는 각자 Fun Factor라는 점수가 존재한다.

리프 노드를 활성화시킴으로써 리프 노드부터 루트까지의 노드 상에 있는 최고 점수를 얻을 수 있다.

단 한번 리프 노드를 활성화하면 경로상에 있는 노드들은 죽게 되고 , 더 이상 그 경로상의 노드들로 점수를 얻을 수 있다.

 

그렇다면 리프 노드들을 활성화시키는 순서에 따라 얻을 수 있는 점수가 달라질 것이다.

문제를 완벽히 이해한지는 잘 모르겠는데 , 설명이 잘못되었거나 이상하면 댓글 부탁드립니다.

 

일단 처음 문제를 봤을 때 , DP 문제라고 생각했다.

서브 트리의 최적해들이 모여 본래 트리의 최적해가 된다고 생각하였고 , 트리 DP 방식으로 접근하였다.

DFS를 재귀적으로 구현해 트리 DP를 적용하였다.

 

풀고 나니 트리 DP가 아닌 것? 같은데 답은 나오니까 아무튼 답은 그냥저냥 내 보았다.

일단 문제를 풀 당시에는 1 <= N <= 1000 인 케이스에 대해서는 억셉이 나왔다.

그런데 10초를 주고 100000까지 억셉이 되는지 안되는지에 대해서는 공개를 해주지 않았다.

 

제출할 당시에는 5초에 1000까지 억셉이고 10초씩이나 주면 100000 되지 않을까?라는 생각으로 그냥 두 개의 Test Set에 대해 정답이 나오길래 그냥 넘어갔다.

오늘 문제를 다시 보려 들어가니 시간 초과가 나있었다...

너무 생각나는 대로 코드를 짠 건가 싶기도 하다.

 

시간을 좀 많이 주는 것 같아 시간 복잡도 생각을 안 하고 구성하여 그런 듯하다.

아마 이 문제의 경우는 다른 좋은 풀이가 있을 것이라 생각하지만 , 리뷰의 목적이므로 코드는 올리기로 했다.

정확한 풀이는 다른 분들의 코드를 참고하시는 것이 좋을 것 같습니다.

 

정답 (Test Set1 , Test Set2 , Test Set3 => TLE ) 제출 코드

#4
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline()) + 1

for idx in range(1,n):
    k = int(sys.stdin.readline())
    c = list(map(int , sys.stdin.readline().split(" ")))
    c = c + [0]
    edge = list(map(int , sys.stdin.readline().split(" ")))
    node = [[] for i in range(k+1)]
    leaf = []
    for i in range(0,len(edge)):
        node[edge[i]].append(i+1)
    for k in range(1,len(node)):
        if len(node[k]) == 0 :
            leaf.append(k)

    dp = [[0,0] for i in range(k+1)]
    for i in leaf:
        dp[i][0] = c[i-1]
        dp[i][1] = c[i - 1]

    visit = [0 for i in range(k+1)]
    def dfs(u):
        visit[u] = 1
        for v in node[u]:
            if visit[v]:
                continue
            dfs(v)
            hap = 0
            mins = float("inf")
            if True:
                for i in node[u]:
                    hap += dp[i][0]
                    if dp[i][1] < mins:
                        mins = dp[i][1]
                if c[u-1] > mins:
                    dp[u][1] = c[u-1]
                    dp[u][0] = hap - mins + c[u-1]
                else:
                    dp[u][1] = mins
                    dp[u][0] = hap

    dfs(0)
    print("Case #%d: %d" %(idx,dp[0][0]))

 

 

 

 

E. Twisty Little Passages

인터랙티브 문제다.

Judge가 프로그램에 대해 입력하면 그에 맞는 출력을 보여주며 답을 내는 방식이다.

인터랙티브의 문제의 경우 백준에서는 본 적 없고 , Atcoder에서 경험해본 적이 있다.

그 당시 풀었던 문제에선 버퍼를 비워주는 방식으로 flush를 사용해야 한다는 점이 기억에 남아있다.

 

아무튼 어차피 소수의 상위 랭크 사람들만 풀어내는 걸 보면 , 내가 못 푸는 문제인 거 같고 깔끔하게 넘겼다.

문제는 미로에 대해서 방이 몇 개 연결되어있는지 답해주면서 미로의 구조? 에 대해서 답하는 문제인 것 같다.

깔끔하게 스킵

 

 

 

 

결과적으로 66점 , 5867등으로 마무리했다.

D번을 너무 대충 풀었나 싶기도 하고 , 조금 아쉬운 부분도 있다.

사실 D번도 처음에 문제를 잘못 이해해서 두어 번 틀리기도 했었는데 , 아무튼 좋은 경험이었던 것 같다.