Google Kick Start 2021 Round A 후기 및 c++ 풀이 (7899등 🤦🏻‍♀️)

구글 킥스타트 코테를 봤다.

1번만 풀었고 3번 풀다가 테스트 케이스만 통과하고 계속 WA 떠서... 영문을 모른채 시험 종료 (알고보니 하찮은 실수 때문이었다.)

못 푼 문제들은 그냥 못본척하고 싶었으나 그래도 다시 풀어보기로 했다.

1. K-Goodness String

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

문제 설명

Problem

Charles defines the goodness score of a string as the number of indices

i

such that

S_{i} \neq S_{N - i + 1}

where

1 \leq i \leq N / 2

(

1

-indexed). For example, the string CABABC has a goodness score of

2

since

S_{2} \neq S_{5}

and

S_{3} \neq S_{4}

.
Charles gave Ada a string

S

of length

N

, consisting of uppercase letters and asked her to convert it into a string with a goodness score of

K

. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to

K

Input

The first line of the input gives the number of test cases,

T

T

test cases follow.
The first line of each test case contains two integers

N

and

K

. The second line of each test case contains a string

S

of length

N

, consisting of uppercase letters.

Output

For each test case, output one line containing Case #

x

y

, where

x

is the test case number (starting from 1) and

y

is the minimum number of operations required to transform the given string

S

into a string with goodness score equal to

K

Limits

Memory limit: 1 GB.

1 \leq T \leq 100

0 \leq K \leq N / 2

문자열에 있어서 K점수란, 간단히 말해 문자열을 반으로 접었을 때 만나는 문자가 서로 다르면 1점을 준다고 할 때 문자열이 갖는 점수이다.

문제 풀이

문제에서 요구하는 것은 문자열 S가 주어졌을 때 문자열 S의 점수가 K가 되도록하는 최소 변형의 수인데, 이는 문자열이 갖는 원래 점수에서 문제에서 주어진 K를 빼고 절대값 처리를 해주면 된다.

따라서 코드는 다음과 같다.

최종 코드

#include <string>
#include <iostream>

using namespace std;

int solution(int n, int k, string s)
{
    int answer = 0;
    for (int i = 0; i < n / 2; ++i)
        if (s[i] != s[n - i - 1])
            ++answer;
    return abs(k - answer);
}

int main()
{
    int num, n, k;
    string s;
    cin >> num;
    for (int i = 0; i < num; ++i)
    {
        cin >> n >> k >> s;
        cout << "Case #" << i + 1 << ": " << solution(n, k, s) << endl;
    }

    return 0;
}

2. L Shaped Plots

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

Kick Start - Google’s Coding Competitions

Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.

codingcompetitions.withgoogle.com

문제 설명

Problem

Given a grid of

R

rows and

C

columns each cell in the grid is either

0

1

.
A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.
A segment is called "good" if all the cells in the segment contain only

1

s.
An "L-shape" is defined as an unordered pair of segments, which has all the following properties:

Each of the segments must be a "good" segment.
The two segments must be perpendicular to each other.
The segments must share one cell that is an endpoint of both segments.
Segments must have length at least $2$ .
The length of the longer segment is twice the length of the shorter segment.

We need to count the number of L-shapes in the grid.

L자 모양은 한 길이가 다른 길이의 두배이고, 작은 쪽 길이가 2 이상인 모양이다.

r*c 사이즈의 0과 1로 이뤄진 매트릭스가 주어지면 L 모양이 몇개나 있는지를 세면 되는 문제이다.

문제 풀이

일단 문제 풀기 전 할일을 정리해보면 이렇다

1. 모든 경우의 수를 중복, 누락 없이 세는 방법
2. 큰 L자 모양을 알아냈을 때 그 안에 속한 모든 L자 모양의 가짓수를 세는 법

1. 모든 경우의 수를 중복, 누락 없이 세는 방법

처음에 문제를 보고 막막하다고 느꼈는데, 경우의 수를 전부 다 돌면서도 중복 케이스를 만들지 않는 방법을 찾는게 어려웠기 때문이다.

시간을 가지고 천천히 생각해보자 방법이 떠올랐는데 이렇다.

두 변이 만나는 점을 기준으로 카운트를 하면 된다.

어떤 L 모양이든 모든 L 모양은 하나의 행과 하나의 열로 만들어져 있다.

예를 들어 r: 6, c: 4 인 매트릭스가 있다고 해보면

i \ j	0	1	2	3
0	1	0	0	0
1	1	0	0	1
2	1	1	1	1
3	1	0	1	0
4	1	0	1	0
5	1	1	1	0

왼 쪽 그림은 i:5 열과 j: 0 행이 이루는 L자 모양이다. 이 케이스에 속하는 모든 L자 모양의 공통 셀은 (5,0)이다.

따라서 i와 j가 이루는 각 셀을 기준으로 L자 모양을 세면 중복, 누락 없이 모든 경우의 수를 셀 수 있을 것이다.

대충 코드를 머릿 속으로 그러보면 i, j 를 갖는 이중 포문 속에서 각 셀에 대해 상하좌우로 뻗어있는 팔(?)의 길이를 구하고 각 조합 (상좌, 상우, 하좌, 하우) 에 대해 L자 모양을 세면 될 것이다.

코드는 아래와 같다.

long long solution(vector<vector<int> > m)
{
    long long answer = 0;
    for (int i = 0; i < m.size(); i++)
    {
        for (int j = 0; j < m[i].size(); j++)
        {
            if (m[i][j] == 1)
            {
                int up(0), down(0), left(0), right(0);
                for (int n = i; n >= 0 && m[n][j] == 1; --n)
                    ++up;
                for (int n = i; n < m.size() && m[n][j] == 1; ++n)
                    ++down;
                for (int n = j; n >= 0 && m[i][n] == 1; --n)
                    ++left;
                for (int n = j; n < m[i].size() && m[i][n] == 1; ++n)
                    ++right;
                countLShapedPlots(up, right, answer);
                countLShapedPlots(up, left, answer);
                countLShapedPlots(down, right, answer);
                countLShapedPlots(down, left, answer);
            }
        }
    }
    return answer;
}

2. 큰 L자 모양을 알아냈을 때 그 안에 속한 모든 L자 모양의 가짓수를 세는 법

1번만 잘 생각해냈으면 2번은 어렵지 않다.

예를 들어 왼쪽같이 가로 3, 세로 6인 큰 L자 모양이 있다고 하면, 일단 가로부터 2부터 시작해서 1씩 늘리며 가로길이*2 < 세로길이 인지를 검사해서 카운트하면 된다.

코드로 구현하면 이렇게 될 것이다.

void countLShapedPlots(int a, int b, long long &answer)
{
    for (int x = 2; x <= a && x * 2 <= b; ++x)
        answer++;
    for (int x = 2; x <= b && x * 2 <= a; ++x)
        answer++;
}

최종코드

#include <vector>
#include <iostream>

using namespace std;

void countLShapedPlots(int a, int b, long long &answer)
{
    for (int x = 2; x <= a && x * 2 <= b; ++x)
        answer++;
    for (int x = 2; x <= b && x * 2 <= a; ++x)
        answer++;
}

long long solution(vector<vector<int> > m)
{
    long long answer = 0;
    for (int i = 0; i < m.size(); i++)
    {
        for (int j = 0; j < m[i].size(); j++)
        {
            if (m[i][j] == 1)
            {
                int up(0), down(0), left(0), right(0);
                for (int n = i; n >= 0 && m[n][j] == 1; --n)
                    ++up;
                for (int n = i; n < m.size() && m[n][j] == 1; ++n)
                    ++down;
                for (int n = j; n >= 0 && m[i][n] == 1; --n)
                    ++left;
                for (int n = j; n < m[i].size() && m[i][n] == 1; ++n)
                    ++right;
                countLShapedPlots(up, right, answer);
                countLShapedPlots(up, left, answer);
                countLShapedPlots(down, right, answer);
                countLShapedPlots(down, left, answer);
            }
        }
    }
    return answer;
}

int main()
{
    int t;
    cin >> t;
    vector<long long> answers;

    for (int test = 0; test < t; test++)
    {
        int r, c;
        cin >> r >> c;
        vector<vector<int> > m(r, vector<int>(c, 0));
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                cin >> m[i][j];
        answers.push_back(solution(m));
    }
    for (int i = 0; i < t; i++)
        cout << "Case #" << i + 1 << ": " << answers[i] << endl;

    return 0;
}

3. Rabbit House

문제 설명

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

Problem

Barbara got really good grades in school last year, so her parents decided to gift her with a pet rabbit. She was so excited that she built a house for the rabbit, which can be seen as a 2D grid with

R

rows and

C

columns.
Rabbits love to jump, so Barbara stacked several boxes on several cells of the grid. Each box is a cube with equal dimensions, which match exactly the dimensions of a cell of the grid.
However, Barbara soon realizes that it may be dangerous for the rabbit to make jumps of height greater than

1

box, so she decides to avoid that by making some adjustments to the house. For every pair of adjacent cells, Barbara would like that their absolute difference in height be at most

1

box. Two cells are considered adjacent if they share a common side.
As all the boxes are superglued, Barbara cannot remove any boxes that are there initially, however she can add boxes on top of them. She can add as many boxes as she wants, to as many cells as she wants (which may be zero). Help hew determine what is the minimum total number of boxes to be added so that the rabbit's house is safe.

Input

The first line of the input gives the number of test cases,

T

T

test cases follow.
Each test case begins with a line containing two integers

R

and

C

.
Then,

R

lines follow, each with

C

integers. The

j

-th integer on

i

-th line,

G_{i, j}

, represents how many boxes are there initially on the cell located at the

i

-th row and

j

-th column of the grid.

Output

For each test case, output one line containing Case #

x

y

, where

x

is the test case number (starting from 1) and

y

is the minimum number of boxes to be added so that the rabbit's house is safe.

Limits

Memory limit: 1 GB.

1 \leq T \leq 100

0 \leq G_{i, j} \leq 2 \cdot 10^{6}

, for all

i

j

.
Test Set 1Time limit: 20 seconds.

1 \leq R, C \leq 50

.
Test Set 2Time limit: 40 seconds.

1 \leq R, C \leq 300

3D로 생각하면 편하다.

블록 쌓기 할 때 처럼 인접한 두 셀의 블록 높이 차가 1이하가 되면 된다.

예를 들어 이런 집이 있다고 하면

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	4	0
0	0	0	0	0

가장 높은 놈을 기준으로 파도가 밀려 나듯이(?) 엘사가 얼음성 쌓듯이(??) 주변 애들에게 블록을 쌓아주면 되는 것이다.

0	0	0	1	0
0	0	1	2	1
0	1	2	3	2
1	2	3	4	3
0	1	2	3	2

주루룩

문제 풀이

모든 셀을 돌면서 각 셀에 대해 사방으로 퍼져나가면서 블록을 쌓아주면 된다.

반복문으로 해도 되긴 할텐데 난 재귀가 더 편해서 재귀 함수로 작성했다.

void recursive(int i, int j, int &answer, vector<vector<int> > &m)
{
    // 종료 조건
    if (i < 0 || i >= m.size() || j < 0 || j >= m[0].size())
    {
        return;
    }
    
    // 상
    if (i - 1 >= 0)
    {
        if (m[i][j] - m[i - 1][j] > 1)
        {
            answer += m[i][j] - m[i - 1][j] - 1;
            m[i - 1][j] = m[i][j] - 1;
            recursive(i - 1, j, answer, m);
        }
    }
    // 하
    if (i + 1 < m.size())
    {
        if (m[i][j] - m[i + 1][j] > 1)
        {
            answer += m[i][j] - m[i + 1][j] - 1;
            m[i + 1][j] = m[i][j] - 1;
            recursive(i + 1, j, answer, m);
        }
    }
    // 좌
    if (j - 1 >= 0)
    {
        if (m[i][j] - m[i][j - 1] > 1)
        {
            answer += m[i][j] - m[i][j - 1] - 1;
            m[i][j - 1] = m[i][j] - 1;
            recursive(i, j - 1, answer, m);
        }
    }
    // 우
    if (j + 1 < m[0].size())
    {
        if (m[i][j] - m[i][j + 1] > 1)
        {
            answer += m[i][j] - m[i][j + 1] - 1;
            m[i][j + 1] = m[i][j] - 1;
            recursive(i, j + 1, answer, m);
        }
    }
    return;
}

최종 코드

일반

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution2(vector<vector<int> > m1, vector<vector<int> > m2)
{
    long long answer = 0;
    for (int i = 0; i < m1.size(); ++i)
    {
        for (int j = 0; j < m1[0].size(); ++j)
        {
            answer += m1[i][j] - m2[i][j];
        }
    }
    return answer;
}

void recursive(int i, int j, int &answer, vector<vector<int> > &m)
{
    if (i < 0 || i >= m.size() || j < 0 || j >= m[0].size())
    {
        return;
    }
    if (i - 1 >= 0)
    {
        if (m[i][j] - m[i - 1][j] > 1)
        {
            answer += m[i][j] - m[i - 1][j] - 1;
            m[i - 1][j] = m[i][j] - 1;
            recursive(i - 1, j, answer, m);
        }
    }
    if (i + 1 < m.size())
    {
        if (m[i][j] - m[i + 1][j] > 1)
        {
            answer += m[i][j] - m[i + 1][j] - 1;
            m[i + 1][j] = m[i][j] - 1;
            recursive(i + 1, j, answer, m);
        }
    }
    if (j - 1 >= 0)
    {
        if (m[i][j] - m[i][j - 1] > 1)
        {
            answer += m[i][j] - m[i][j - 1] - 1;
            m[i][j - 1] = m[i][j] - 1;
            recursive(i, j - 1, answer, m);
        }
    }
    if (j + 1 < m[0].size())
    {
        if (m[i][j] - m[i][j + 1] > 1)
        {
            answer += m[i][j] - m[i][j + 1] - 1;
            m[i][j + 1] = m[i][j] - 1;
            recursive(i, j + 1, answer, m);
        }
    }
    return;
}

int main()
{
    int num, row, col;
    cin >> num;
    for (int t = 0; t < num; ++t)
    {
        cin >> row;
        cin >> col;
        vector<vector<int> > m(row, vector<int>(col, 0));
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                cin >> m[i][j];
            }
        }
        vector<vector<int> > temp(m);
        cout << "Case #" << t + 1 << ": " << solution2(m, temp) << endl;
    }

    return 0;
}

디버깅 용 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

void printMatrix(vector<vector<int> > m)
{
    for (int i = 0; i < m.size(); ++i)
    {
        for (int j = 0; j < m[0].size(); ++j)
        {
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
}

long long solution(vector<vector<int> > m1, vector<vector<int> > m2)
{
    long long answer = 0;
    for (int i = 0; i < m1.size(); ++i)
    {
        for (int j = 0; j < m1[0].size(); ++j)
        {
            answer += m1[i][j] - m2[i][j];
        }
    }
    return answer;
}

void recursive(int i, int j, int &answer, vector<vector<int> > &m)
{
    if (i < 0 || i >= m.size() || j < 0 || j >= m[0].size())
    {
        return;
    }
    if (i - 1 >= 0)
    {
        if (m[i][j] - m[i - 1][j] > 1)
        {
            answer += m[i][j] - m[i - 1][j] - 1;
            m[i - 1][j] = m[i][j] - 1;
            recursive(i - 1, j, answer, m);
        }
    }
    if (i + 1 < m.size())
    {
        if (m[i][j] - m[i + 1][j] > 1)
        {
            answer += m[i][j] - m[i + 1][j] - 1;
            m[i + 1][j] = m[i][j] - 1;
            recursive(i + 1, j, answer, m);
        }
    }
    if (j - 1 >= 0)
    {
        if (m[i][j] - m[i][j - 1] > 1)
        {
            answer += m[i][j] - m[i][j - 1] - 1;
            m[i][j - 1] = m[i][j] - 1;
            recursive(i, j - 1, answer, m);
        }
    }
    if (j + 1 < m[0].size())
    {
        if (m[i][j] - m[i][j + 1] > 1)
        {
            answer += m[i][j] - m[i][j + 1] - 1;
            m[i][j + 1] = m[i][j] - 1;
            recursive(i, j + 1, answer, m);
        }
    }
    return;
}

int main()
{
    int num, row, col;
    cin >> num;
    for (int t = 0; t < num; ++t)
    {
        cin >> row;
        cin >> col;
        vector<vector<int> > m(row, vector<int>(col, 0));
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                cin >> m[i][j];
            }
        }
        vector<vector<int> > temp(m);
        cout << "Case #" << t + 1 << ": " << solution(m, temp) << endl;
    }

    return 0;
}

/*
3
1 3
3 4 3
1 3
3 0 0
3 3
0 0 0
0 2 0
0 0 0

1
5 9
0 0 0 0 0 0 0 0 7
3 0 0 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 5

1
5 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

1
5 9
0 0 0 0 1000 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
*/

4. Checksum

문제 설명

Problem

Grace and Edsger are constructing a

N \times N

boolean matrix

A

. The element in

i

-th row and

j

-th column is represented by

A_{i, j}

. They decide to note down the checksum (defined as bitwise XOR of given list of elements) along each row and column. Checksum of

i

-th row is represented as

R_{i}

. Checksum of

j

-th column is represented as

C_{j}

.
For example, if

N = 2

A = [\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}]

, then

R = [\begin{matrix} 1 & 0 \end{matrix}]

and

C = [\begin{matrix} 0 & 1 \end{matrix}]

.
Once they finished the matrix, Edsger stores the matrix in his computer. However, due to a virus, some of the elements in matrix

A

are replaced with

- 1

in Edsger's computer. Luckily, Edsger still remembers the checksum values. He would like to restore the matrix, and reaches out to Grace for help. After some investigation, it will take

B_{i, j}

hours for Grace to recover the original value of

A_{i, j}

from the disk. Given the final matrix

A

, cost matrix

B

, and checksums along each row (

R

) and column (

C

), can you help Grace decide on the minimum total number of hours needed in order to restore the original matrix

A

Input

The first line of the input gives the number of test cases,

T

T

test cases follow.
The first line of each test case contains a single integer

N

.
The next

N

lines each contain

N

integers representing the matrix

A

j

-th element on the

i

-th line represents

A_{i, j}

.
The next

N

lines each contain

N

integers representing the matrix

B

j

-th element on the

i

-th line represents

B_{i, j}

.
The next line contains

N

integers representing the checksum of the rows.

i

-th element represents

R_{i}

.
The next line contains

N

integers representing the checksum of the columns.

j

-th element represents

C_{j}

Output

For each test case, output one line containing Case #

x

y

, where

x

is the test case number (starting from 1) and

y

is the minimum number of hours to restore matrix

A

Limits

Memory limit: 1 GB.

1 \leq T \leq 100

- 1 \leq A_{i, j} \leq 1

, for all

i, j

1 \leq B_{i, j} \leq 1000

, for

i, j

where

A_{i, j} = - 1

, otherwise

B_{i, j} = 0

0 \leq R_{i} \leq 1

, for all

i

0 \leq C_{j} \leq 1

, for all

j

.
It is guaranteed that there exist at least one way to replace

- 1

A

with

0

1

such that

R

and

C

as satisfied.

스도쿠로 생각하면 편하다.

만약 각 행이나 열에 모르는 숫자가 하나 밖에 없으면 그 숫자를 바로 알 수 있다.

그러나 모르는 숫자가(-1, 바이러스 공격 받은 패킷) 두개 이상이면 둘 중 하나는 시간을 들여 복구를 해야한다.

이 때 비용 행렬 B를 참고해 되도록 복구에 시간이 덜 걸리는 셀을 복구해서 모든 셀을 복구하는데에 들어가는 최소 시간을 구하면 되는 것이다.

문제 풀이

이건 알고리즘 이론 공부가 좀 필요할 것 같다.

강해져서 돌아오겠습니다...

최종 코드

총평

1. K-Goodness String

문제 설명

Problem

Input

Output

Limits

문제 풀이

최종 코드

2. L Shaped Plots

문제 설명

Problem

문제 풀이

1. 모든 경우의 수를 중복, 누락 없이 세는 방법

2. 큰 L자 모양을 알아냈을 때 그 안에 속한 모든 L자 모양의 가짓수를 세는 법

최종코드

3. Rabbit House

문제 설명

Problem

Input

Output

Limits

문제 풀이

최종 코드

일반

디버깅 용 코드

4. Checksum

문제 설명

Problem

Input

Output

Limits

문제 풀이

최종 코드

총평

티스토리툴바