구글 킥스타트(Kickstart) 2021 Round A 문제풀이

문제 풀고 나중에 혼자 다시볼겸 남기는 포스트

Prob.1  K-Goodness String

입력 받은 문자열을 좌우대칭이 되게 만드는게 목표
그냥 깊게 생각할것도 없이 좌우 끝으로 부터 하나씩 비교하면서 서로 다른 경우 횟수를 기록해주고 이 횟수와 주어진 K와의 차가 답이 된다

 

test_n = int(input())


for tn in range(test_n):
    string_len, k = map(int, input().split(' '))

    string = input()

    score = 0
    ans = 0

    for i in range(0, int(string_len/2)):
        if string[i] != string[string_len-i-1]:
            score += 1
    ans = abs(score - k)

    print('Case #{}: {}'.format(tn+1, ans))

Prob.2  L Shaped Plots

가로와 세로 길이가 정확히 2배 차이나는 L모양을 찾는 문제
보자마자 완전탐색 문제라 생각하고 모든 좌표를 돌면서 L모양이 있는지 없는지 검사를 하였다 그러자 마지막 testcase에서 시간초과로 통과하지 못했다

완전탐색 문제는 확실한대 시간초과가 나니 아무래도 각 좌표마다 L모양이 있는지 탐색하는 방법에 문제가 있다고 판단하고 미리 모든 좌표의 상하좌우 블록수를 각각 기록한 뒤 이를 토대로 각 좌표를 돌며 L모양을 찾으니 통과하였다

L모양의 꺽이는 블록으로부터 긴쪽 방향의 블록수 A와 짧은쪽 방향의 블록수를 B라 하면 그 L모양이 총 포함하는 L모양은 min(A/2, B)-1개가 되므로 이 방법으로 모든방향을 검사해주는식으로 코드를 작성했다

 

test_n = int(input())

import copy


for tn in range(test_n):
    ans = 0

    row, col = map(int, input().split(' '))
    m = []

    for _ in range(row):
        m.append(list(map(int, input().split(' '))))

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

    for i in range(1,row):
        for j in range(col):
            if m[i][j] == 1:
                U[i][j] += U[i-1][j]

    for i in range(row-2, -1, -1):
        for j in range(col):
            if m[i][j] == 1:
                D[i][j] += D[i+1][j]

    for i in range(row):
        for j in range(1,col):
            if m[i][j] == 1:
                L[i][j] += L[i][j-1]

    for i in range(row):
        for j in range(col-2, -1, -1):
            if m[i][j] == 1:
                R[i][j] += R[i][j+1]


    for x in range(row):
        for y in range(col):
            if m[x][y] == 0:
                continue

            ans += max(min(U[x][y]//2, R[x][y])-1, 0)
            ans += max(min(R[x][y]//2, U[x][y])-1, 0)

            ans += max(min(D[x][y]//2, R[x][y])-1, 0)
            ans += max(min(R[x][y]//2, D[x][y])-1, 0)

            ans += max(min(D[x][y]//2, L[x][y])-1, 0)
            ans += max(min(L[x][y]//2, D[x][y])-1, 0)

            ans += max(min(U[x][y]//2, L[x][y])-1, 0)
            ans += max(min(L[x][y]//2, U[x][y])-1, 0)



    print('Case #{}: {}'.format(tn+1, ans))

Prob.3  Rabbit House

우선순위 큐를 사용해서 해결했다

1. 모든 블록을 우선순위 큐에 집어 넣는다
2. 가장 높은 블록 하나를 꺼낸다
3. 만약 꺼낸 블록과 주변 블록과의 높이 차가 1보다 크면 차가 1만큼 나게 만들어 준다
4. 이 새로 지은 블록을 우선순위 큐에 집어 넣는다
5. 2~4 과정을 큐가 빌때까지 반복한다

#include <iostream>
#include <queue>
#include <cstdlib>

using namespace std;

int map[301][301];

void solve(){
    int R,C;
    priority_queue<pair<int, int>> pq;

    cin >> R >> C;
    for(int r=1; r<=R; r++)
        for(int c=1; c<=C; c++){
            cin >> map[r][c];
            pq.push({map[r][c], r*1000 + c});
        }

    long long ans =0;
    while(!pq.empty()){

        int h = pq.top().first;
        int r = pq.top().second / 1000;
        int c = pq.top().second % 1000;

        if(1 <= r-1 && map[r][c] - map[r-1][c] > 1){
            ans += map[r][c] - map[r-1][c] -1;
            map[r-1][c] = map[r][c] - 1;
            pq.push({map[r-1][c], (r-1)*1000 + c});
        }

        if(r+1 <= R && map[r][c] - map[r+1][c] > 1){
            ans += map[r][c] - map[r+1][c] -1;
            map[r+1][c] = map[r][c] - 1;
            pq.push({map[r+1][c], (r+1)*1000 + c});
        }

        if(1 <= c-1 && map[r][c] - map[r][c-1] > 1){
            ans += map[r][c] - map[r][c-1] -1;
            map[r][c-1] = map[r][c] - 1;
            pq.push({map[r][c-1], (r)*1000 + c-1});
        }

        if(c+1 <= C && map[r][c] - map[r][c+1] > 1){
            ans += map[r][c] - map[r][c+1] -1;
            map[r][c+1] = map[r][c] - 1;
            pq.push({map[r][c+1], (r)*1000 + c+1});
        }


        pq.pop();
    }

    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();
    }


}

Prob.4  Checksum

문제를 읽고 이해하는데 오랜시간이 걸린 문제
xor연산 결과를 제공하였는데 이 xor연산 결과 값으로부터 원본값을 찾을려면 속한 행, 열에서 원본값을 모르는 변수가 1개 이하여야 한다
뭔 소리냐하면

 

특정 행, 열	xor 연산 값
01?10	1
01?1?0	1

이와 같이 있을 때, 첫번째 경우는 ?에 1이 들어가는 것을 알지만 두번째 경우에서는 10, 01 같이 2가지 경우 모두 가능하다.

다시 문제로 돌아오면 특정 행, 열에서 -1 값이 하나면 바로 그 값을 계산하여 알 수 있다는 소리다

만약 특정 좌표의 원본 값을 하나 찾았는데, 그로인해 그 좌표가 속한 행, 열에서 -1 가 1개가 되면 그 값도 자동으로 알 수 있게 된다

즉 연쇄작용으로 값을 파바바바박 알 수 있게 되는 경우가 생길 수 있다

각 행, 열 th를 노드라 보고 -1의 cost를 엣지라고 생각하면 아래와 같이 된다
엣지가 없는 노드는 이미 값을 아는 경우에 해당하고 엣지가 하나만 있는경우에는 cost없이 계산하여 바로 알수 있음을 의미하게 된다
근데 만약 그래프에 사이클이 없다고 생각하면 path의 끝 노드는 엣지가 하나일것이고 바로 원본값을 찾을수 있음을 의미한다 그리고 이 노드로부터 연쇄작용으로 파바바바박 다른 값들도 차례대로 알 수 있게 된다

즉 답을 찾기 위해서, 최소의 엣지를 제거하여 (cost를 지불) 그래프에 사이클이 존재하지 않도록 하면 된다는것을 알 수 있다

사진출처- google kickstart

제거해야하는 엣지를 찾는것보다 제거되지 않을 엣지들을 찾는게 더 쉽다 나같은 경우에는 크루스칼 알고리즘을 이용하여 각 유니온들의 최대신장트리 찾는 방법으로 하였다

#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();
    }


}