[Google Kick Start] 2021 Round A

문제 1

codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cca3

Kick Start - Google’s Coding Competitions

풀이

문제가 영어여서 해석하는데 애를 먹었지만 이번 라운드 중 가장 쉬운 문제였다.

abs를 안해줘서 틀렸었다ㅎ

T = int(input())

for i in range(T):
    N, K = map(int, input().split())
    string = input()
    good = 0
    for j in range(int(N/2)):
        if(string[j] != string[N-1-j]):
            good += 1
    print("CASE #" + str(i+1) + ":", abs(K - good))

---

문제 2

codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c509

Kick Start - Google’s Coding Competitions

풀이

지난 주에 풀면서 나름대로 로직은 세워봤는데 도저히 구현이 안 돼서 못 풀었다.

그래서 한국 1등의 코드를 분석했다.

import copy

#테스트케이스 수 입력받음
tc = int(input())
for _ in range(tc):
  n, m = map(int, input().split())
  #그리드 저장
  a = [list(map(int, input().split())) for _ in range(n)]

  U = copy.deepcopy(a)
  D = copy.deepcopy(a)
  L = copy.deepcopy(a)
  R = copy.deepcopy(a)

  #이어진 블록 수 만큼 누적시킨다.
  for i in range(1, n):
    for j in range(m):
      if a[i][j] > 0: U[i][j] += U[i-1][j]

  for i in range(n-2, -1, -1):
    for j in range(m):
      if a[i][j] > 0: D[i][j] += D[i+1][j]

  for i in range(n):
    for j in range(1, m):
      if a[i][j] > 0: L[i][j] += L[i][j-1]

  for i in range(n):
    for j in range(m-2, -1, -1):
      if a[i][j] > 0: R[i][j] += R[i][j+1]

  #L형의 개수를 리턴
  def f(x, y):
  	#서있는 L형, 누운 L형을 각각 셈. 
    #타일이 한 개일 때에는 L형 성립 안 되기 때문에 1 빼줌
    #타일이 1개일 때 -1이 리턴되기 때문에 0과 비교해서 큰 쪽을 더함
    c = max(0, min(x, y//2)-1)
    c += max(0, min(y, x//2)-1)
    return c

  #위, 아래 / 왼, 오를 조합함
  res = 0
  for i in range(n):
    for j in range(m):
      t = 0
      if a[i][j] == 1:
        t += f(U[i][j], L[i][j])
        t += f(U[i][j], R[i][j])
        t += f(D[i][j], L[i][j])
        t += f(D[i][j], R[i][j])
      res += t

  # print(U[2][0], D[2][0], L[2][0], R[2][0])
  print("Case #{}: {}".format(_+1, res))

 

이해를 돕기 위한 표

a	U	D	L	R
1 0 0 1 0 1   1 0 0  1 1 0	1 0 0 1 0 1   1 0 0  1 1 0	4 0 0 3 0 1 2 0 0 1 1 0	1 0 0 1 0 1   1 0 0  1 2 0	1 0 0 1 0 1   1 0 0  1 2 0

누적시킬 생각을 한 게 키포인트인 것 같다. L형을 세는 방식도 엄청 간단하다,, 진자 개천재

---

문제 3

codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14

Kick Start - Google’s Coding Competitions

풀이

주어진 그리드에서 인접한 칸과 2이상 차이가 나지 않도록 추가하는 박스의 최소 개수를 구하는 문제이다.

생각한 로직은 다음과 같다.

1. 박스가 가장 많은 칸을 찾는다.

2. 인접한 칸에 1씩 차이나게 박스를 추가한다.

3. 방문했던 칸을 큐에 넣는다.

4. 큐 안의 박스가 가장 많은 칸을 찾는다.

위 방식대로 풀며 구현이 막히는 부분은 다른 분의 코드를 참고했다.

그런데 time limit이 계속 떴다,, 다른사람의 코드대로 의심되는 부분을 차례차례 고쳐가는데도 time limit이 떴다

그래서 다른 분의 코드를 그냥 가져다가 넣어봤는데 타임리밋 뜸

라운드 열리는 당일에만 서버를 더 준비하는?건가?ㅜ 아무튼 그래서 그대로 놔둠

from queue import PriorityQueue
import copy

q = PriorityQueue()

T = int(input())

for t in range(T):
    R, C = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(R)]
    ans = copy.deepcopy(grid)
    
    for i in range(R):
        for j in range(C):
            q.put((2000000 - grid[i][j], (i,j)))

    while not q.empty():
        node = q.get()[1]

        directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        for d in directions:
            r, c = node[0] + d[0], node[1] + d[1]
            if not (0 <= r < R and 0 <= c < C): continue
            if ans[node[0]][node[1]] - ans[r][c] > 1:
                ans[r][c] = ans[node[0]][node[1]] - 1
                q.put((2000000 - ans[r][c], (r,c)))

    count = 0    
    for i in range(R):
        for j in range(C):
            count += ans[i][j] - grid[i][j]
    
    print("CASE #" + str(t+1) + ": " + str(count))

---

문제 4

codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c2c3

Kick Start - Google’s Coding Competitions

풀이

문제를 이해하는데 오래 걸렸다. XOR이 1이 홀수개면 1, 짝수개면 0을 반환하는 것을 몰랐다.;

다른 분들의 블로그를 참고했는데, 문제를 해석해나가니 결국 최소신장트리, 크루스칼알고리즘 문제였다.

킥스타트 사이트를 뒤지고 뒤져서 겨우 파이썬 코드를 찾긴 했는데, 너무; 난해해서 해석을 포기했다.

for case in range(1,int(input())+1):
    n=int(input())
    m=[list(map(int,input().split())) for i in range(n)]
    c=[list(map(int,input().split())) for i in range(n)]
    #의미없는 체크섬 받기
    input()
    input()
    edges=[]
    
    for i in range(n):
        for j in range(n):
            if m[i][j]==-1:
                edges.append((c[i][j],~i,j))
    #간선 정렬
    #튜플의 경우 첫 번째 원소 순으로 정렬, 첫 번째 원소가 같으면 두 번째를 기준으로 정렬...
    edges.sort()

    d={i:{'head':i,'depth':0} for i in range(-n,n)}

    price=0
    for cost,a,b in edges[::-1]:      
        while d[a]['head']!=a:
            d[a]['head']=d[d[a]['head']]['head']
            a=d[a]['head']
        while d[b]['head']!=b:
            d[b]['head']=d[d[b]['head']]['head']
            b=d[b]['head']
        if a==b:
            price+=cost
        else:
            if d[a]['depth']>d[b]['depth']:
                d[b]['head']=a
            else:
                d[a]['head']=b
                d[b]['depth']=max(d[b]['depth'],d[a]['depth']+1)

    print('Case #',case,': ',price,sep='')
        

 

 

그래서 C++코드를 대신 해석하기로함

크루스칼 알고리즘을 활용했다

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstdlib>
#include <vector> 

using namespace std;

int map[501][501];
int cost[501][501];
int R[501];
int C[501];
int N;
int root[1003];

int find(int x){
	//자기자신이 부모일때
    if(root[x]==x) return x;
	
	
    int y = find(root[x]);
    root[x] = y;
    return y;
}

void solve(){
    long long ans = 0;
    int tagets = 0;

    cin >> N;

    priority_queue<pair<int, pair<int, int>>> q;

    for(int r=1; r<=N; r++)
        for(int c=1; c<=N; c++){
            cin >> map[r][c];
            if(map[r][c]== -1)
                tagets += 1;
        }

    for(int r=1; r<=N; r++)
        for(int c=1; c<=N; c++)
            cin >> cost[r][c];

    for(int r=1; r<=N; r++)
        cin >> R[r];

    for(int r=1; r<=N; r++)
        cin >> C[r];   

    for(int r=1; r<=N; r++)
        for(int c=1; c<=N; c++)
            if(cost[r][c] != 0){
                q.push({cost[r][c], {r, c}});
                ans += cost[r][c];
            }


    for(int i =1; i<=2*N; i++) root[i] = i;

    while(q.size()){
        int cos = q.top().first;
        int r = q.top().second.first;
        int c = q.top().second.second;
        q.pop();
		
        
        if (find(r) != find(N+c) ){
            root[find(N+c)] = find(r);
            ans -= cos;
        }
    }


    cout<<ans<<"\n";
}




int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int testcase;

    cin >> testcase;

    for(int t =1; t<= testcase; ++t){
        cout << "Case #"<<t<<": ";
        solve();
    }


}