KPU S/W 경진대회 본선 후기

본선일정은 2020.10.14 (수)에 13:30 ~ 17:00까지로 예선 후 1주일 뒤에 잡혀있었다.

수요일 본선 당일 12시 반까지 있던 수업을 마치고 기숙사에 들려 노트북을 챙겨 시험장소인 소강당으로 향했다.
도착해서 점심으로 서브웨이와 스프라이트를 받고 자리를 잡자마자 샌드위치를 허겁지겁 먹어치웠다.
(아침 점심을 안먹었더니 배가 너무 고팠었다…😂)

그런데, 사회적 거리 두기때문에 좀 넓은 곳에서 시험 보려고 소강당에서 시험을 봤으나, 소강당이 일반 책상이 아닌, 팔걸이에 간이 받침대가 숨어있는(?) 그런 의자라서 불편했다.



📢 시험 시작 전 OT

13:30분에 교수님과 인사하고 강당에서 시험을 보다보니 멀티탭 문제로 시간좀 지체하고 시험 룰 같은 거 이것 저것 설명하다보니 14:00쯤 되어서야 본격적인 시험이 시작되었다.



📝 시험 시작

시험은 총 8문제가 출제 되었고, 시작하자마자 1번 문제인 후위표기식 문제를 건너뛰고, 2번 문제부터 풀기 시작했다.


1️⃣ Postfix 표현식


문제 보기



2️⃣ 다음 순열


문제 보기


주어진 규칙대로 알파벳을 더해주고 조건 만족할때까지 while을 도는 쉬운 문제여서 쉽게 풀 수 있겠다. 하고 시작했는데, 중간에 'p' + 'l'이 어떻게 f가 나오는 지 규칙을 이해를 잘 못해서 많이 헤맸던 문제였다.

풀면서 머리속에서 너무 꼬여서 거의 다 풀었음에도 불구하고 결국 다음 문제로 넘어가는 것을 선택했다.

규칙에서 ‘b’ + ‘z’ = ‘ba’ 가 나온 것을 보고 ‘c’ + ‘z’ = ‘bb’가 아닌 ‘ca’가 될 것이라고 생각 했던 내 멍청함을 탓한다..ㅠㅠ😥


아래는 시험이 끝난 후 차분히 코드 수정을 한 코드이다. cal함수에서 덧셈 규칙의 잘못 이해한 부분만 수정해주니 잘 돌아가는 것을 볼 수 있었다.

코드 보기 ( 접기 / 펼치기 )
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

//abcde/fghij/klmno/pqrst/uvwxy/z
char out_alp(int num)
{
    switch (num)
    {
    case 0:
        return 'a';
    case 1:
        return 'b';
    case 2:
        return 'c';
    case 3:
        return 'd';
    case 4:
        return 'e';
    case 5:
        return 'f';
    case 6:
        return 'g';
    case 7:
        return 'h';
    case 8:
        return 'i';
    case 9:
        return 'j';
    case 10:
        return 'k';
    case 11:
        return 'l';
    case 12:
        return 'm';
    case 13:
        return 'n';
    case 14:
        return 'o';
    case 15:
        return 'p';
    case 16:
        return 'q';
    case 17:
        return 'r';
    case 18:
        return 's';
    case 19:
        return 't';
    case 20:
        return 'u';
    case 21:
        return 'v';
    case 22:
        return 'w';
    case 23:
        return 'x';
    case 24:
        return 'y';
    case 25:
        return 'z';
    default:
        break;
    }
    return 0;
}

bool check(string str)
{
    int i, j = str.length() - 1;
    for (i = 0; i < str.length() / 2; i++, j--)
    {
        if (str[i] != str[j])
            return false;
    }
    return true;
}
void cal(string &str, string r_str, string &ans)
{
    char a2, b2;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        int a = (str[i] - 'a' + r_str[i] - 'a') / 26;
        int b = (str[i] - 'a' + r_str[i] - 'a') % 26;
        if (a == 1)
            str[i - 1] += a;

        ans += out_alp(b);
    }
}

void rule(string &str)
{
    string ans = "";
    string r_str = str;

    reverse(r_str.begin(), r_str.end());
    cal(str, r_str, ans);
    str = ans;
}

int main()
{
    string input;
    cin >> input;

    while (!check(input))
    {
        rule(input);
    }

    cout << input;
    return 0;
}



3️⃣ 조이 스틱


문제 보기


과거에 프로그래머스를 통해 풀어본 문제였기에 수월하게 풀이를 진행 했다.

input의 문자열 길이만큼 초기값 A로 세팅을 해주고, 알파벳의 중간값인 M을 기준으로 작으면 알파벳 순번을, 크다면 역으로 셀 경우가 작게 나오기 때문에 Z에서 char 번호만큼 빼준 값을 통해 각 알파벳을 선택하기위한 조이스틱 횟수를 answer에 더해줬다.

또한, input2의 case처럼 JAN에서 첫번째 글짜를 J로 설정하고 다음 글자를 선택하려고 할때 두번째 글짜는 A가있는 오른쪽으로 이동하는 것보다 왼쪽으로 이동하는 것이 더 적은 횟수를 사용할 수 있기 때문에 조이스틱을 mov하는 과정도 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우를 비교하여 더 최선인 방향을 선택하는 식으로 풀이를 진행했다.


코드 보기 ( 접기 / 펼치기 )
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int sol(string name) {
    int answer = 0;
    int i=0;
    string tmp(name.length(),'A');

    while(1){
        tmp[i] = name[i];
        answer += (name[i] <= 'M') ? (name[i] - 'A') : ('Z' - name[i] + 1) ;
        if(!tmp.compare(name)) break;

        for(int mov = 1; mov < name.length() ; mov++){
            if(name [(i + mov) % name.length()] != tmp[(i + mov) % name.length()]){
                i =  (i + mov) % name.length();
                answer += mov;
                break;
            }
            else if(name [(i + name.length() - mov) % name.length()] != tmp[(i + name.length() - mov)% name.length()]){
                i = ( i + name.length() - mov ) % name.length();
                answer += mov;
                break;
            }
        }
    }
    return answer;
}
int main(){
    string input;
    cin >> input;
    cout << sol(input);
    return 0;
}



두 문제를 풀이하고 (정확히는 한문제다..)
남은 시간을 보니 모든 문제는 풀기에 가망이 없어 보였기 때문에 집중해서 풀어낼 문제를 선택해야 했다.

현재 문제 상황을 보니 의외로 끝의 문제들이 합격률이 괜찮았고, 뒷 문제일수록 배점이 좋았기 때문에 이때부터 뒤의 문제부터 풀이를 해나갔다.


4️⃣ 사회적 거리두기 2


문제 보기



5️⃣ 중요한 교차로


문제 보기



6️⃣ 여행 경로


문제 보기


문제를 보고 dfsbfs로 풀면 되겠다 생각하고 접근했으며, 도착하기까지의 경로가 여러개 일 수 있기 때문에 모든 경로를 저장하는 배열을 전역변수로 선언하여 경로를 구하고 알파벳순으로 sort하여 가장 앞의 경로를 답으로 제출하는 식으로 풀이를 진행했다.

time limit 풀이를 진행하고 보니 4개의 case중 1개의 case가 time Limit으로 부분 통과 하였다.

모든 경로를 계산 하는 것 때문이 아닐까 싶다… 지금 생각해보니 먼저 input의 경로를 sort하고 dfs를 진행했다면 괜찮았을 것 같다.


코드 보기 ( 접기 / 펼치기 )
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<vector<string>> all_routes;

void dfs(vector<vector<string>> tickets, vector<bool> &visited, int cnt, int start, vector<string> &route)
{
    visited[start] = true;
    route.push_back(tickets[start][0]);

    if (cnt == tickets.size())
    {
        route.push_back(tickets[start][1]);
        all_routes.push_back(route);
        route.pop_back();
        return;
    }
    for (int i = 0; i < tickets.size(); i++)
    {
        if (!visited[i] && tickets[start][1] == tickets[i][0])
        {
            dfs(tickets, visited, cnt + 1, i, route);
            visited[i] = false;
            route.pop_back();
        }
    }
}

vector<string> sol(vector<vector<string>> tickets)
{
    vector<string> route;
    vector<bool> visited;
    int cnt = 1;

    for (int i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == "ICN")
        {
            visited.assign(tickets.size(), false);
            route.clear();
            dfs(tickets, visited, cnt, i, route);
        }
    }
    sort(all_routes.begin(), all_routes.end());
    return all_routes[0];
}
int main()
{
    int N;
    cin >> N;
    vector<vector<string>> tickets(N, vector<string>(2, ""));
    vector<string> answer;
    for (int i = 0; i < N; i++)
    {
        cin >> tickets[i][0] >> tickets[i][1];
    }

    answer = sol(tickets);

    for (auto n : answer)
    {
        cout << n << endl;
    }
    return 0;
}



7️⃣ 위성 이미지


문제 보기


7번 문제도 dfs/bfs를 이용하여 풀었으며, 단순히 개수만 세면 되기 때문에 6번 문제보다 더 쉽게 풀이할 수 있었다. bfs를 이용해서 문제를 풀이 했고, 미로 찾기같이 4방향으로만 움직이는 것이 아닌 대각선으로도 움직일 수 있기 때문에 총 8방향에 대해서 bfs를 수행했다.


코드 보기 ( 접기 / 펼치기 )
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int M, N;
int K;
int answer = 0, answer_max = 0;
int dir[8][2] = {{-1, 0}, {-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {1, 0}, {0, -1}, {0, 1}};

void bfs(vector<vector<bool>> &map, int S_x, int S_y)
{
    int r = 1; //구름 넓이

    queue<pair<int, int>> q;
    map[S_y][S_x] = true;
    q.push(make_pair(S_x, S_y));
    int x,y,next_x,next_y;
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            next_x = x + dir[i][0];
            next_y = y + dir[i][1];

            if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && map[next_y][next_x] == false)
            {
                map[next_y][next_x] = true;
                q.push(make_pair(next_x, next_y));
                r++;
            }
        }
    }
    if (K < r)
    {
        answer_max = (answer_max < r) ? r : answer_max;
        answer += 1;
    }
}

int main()
{

    cin >> M >> N;

    vector<vector<bool>> arr(M, vector<bool>(N, true));

    for (int i = 0; i < M; i++)
    {
        int j = 0;
        string str;
        cin >> str;
        for (auto c : str)
        {
            if (c != '#')
            {
                arr[i][j] = false;
            }
            j++;
        }
    }
    cin >> K;

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (arr[i][j] == false)
            {
                bfs(arr, j, i);
            }
        }
    }
    cout << answer << " " << answer_max;
    return 0;
}



8️⃣ 목재 총량


문제 보기


마지막 문제를 풀이하는 데 30분쯤 남아 있는 상태였다.

그래서 아까 풀다 못풀었던 회문 생성기를 마저 풀까, 이 문제를 풀까 하다가 dp를 이용하는 문제이기에 쉽게 풀 수있을 거라 생각하고 마지막 문제를 택했다.
문제에서 친절하게 dp를 이용해서 풀이하라고 설명이 되있다.


각 행에 속한 값을 계속 뒤로 밀며 더해주어 dp 배열을 완성해주고, 값을 찾을 때는 각 행의 도착지점의 dp열의 값에서 시작지점의 앞의 dp배열 값을 빼는 식으로 규칙을 찾아 코드를 작성했다.



2분이 채 안남았을 때, forest값을 입력 받으면서 dp값을 계산해 줄때 forest와 dp배열을 잘 못 입력한 것을 발견하고 수정을 했지만, 또 답이 틀리게 나왔다.

포기안하고 틀린 부분을 찾다가 마지막 1분도 안남았을 때 쯤에 반복문 j < dy - 1j < dy 로 작성한 것을 보고 고쳐 답을 제출하려는 찰나에 17:00가 되어 칼같이 마감이 되어 제출을 못했다.. 😭


코드 보기 ( 접기 / 펼치기 )
#include <iostream>
#include <vector>

using namespace std;
int M, N;

int main()
{

    cin >> M >> N;
    vector<vector<int>> forest(M, vector<int>(N, 0));
    vector<vector<int>> dp(M, vector<int>(N, 0));

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> forest[i][j];
            if (j != 0)
            {
                dp[i][j] += dp[i][j - 1] + forest[i][j];
            }
            else{
                dp[i][j] += forest[i][j];
            }
        }
    }
    int C;
    cin >> C;
    vector<int> answer(C, 0);

    for (int i = 0; i < C; i++)
    {
        int sx, sy, dx, dy;
        cin >> sy >> sx >> dy >> dx;

        for (int j = sy - 1; j < dy - 1; j++)
        {
            if (sx - 1 != 0)
            {
                answer[i] += dp[j][dx - 1] - dp[j][dx - 2];
            }
            else
            {
                answer[i] += dp[j][dx];
            }
        }
    }
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << endl;
    }

    return 0;
}



🏆 시험 결과


점수 집계는 바로 되어 시험이 끝나자마자 시상식을 진행 했다.
시상식은 간단하게 사진을 찍는 정도만 했다.

10만원의 목표는 달성을 했지만 사람 욕심이 끝이 없다고 30만원 커트라인인 8등 점수 80점을 보고 마지막 문제를 제출만 했으면 30만원 이었을 텐데 하는 아쉬움이 남았다.
(핑계이기도 하고, 이건 다른 분들도 똑같지 않았을까 싶다. 더 공부해야겠다고 느꼈다.)


17학번이 158점으로 1등을 했고 예선전에서 1등 했던 19학번은 120점으로 3등했다.

은근 10만원 커트라인이 높지 않고 한문제 반 맞는 정도 였으며, 게임공학과가 참여도 많이 했고 점수도 평균적으로 높게 나온 거 같았다.


제대로 된 책상이 아닌 무릎에 올려놓고 4시간을 코딩 했더니 끝나고 나서 허리와 목이 너무 아팠다.
(이 부분은 교수님이 사회적 거리두기 때문에 장소가 마땅치 않았다고 미안하다고 계속 사과하시긴 했다..)

마지막으로 퇴장하면서 기념품을 하나씩 주셨는데, 꽤 실용적이고 디자인도 나쁘지 않은 10,000mAh 보조 배터리가 들어있었다.
가지고 있는 20,000mAh 보조배터리가 무거웠는데 마침 잘됬다 싶었다.

못 풀었던 3문제는 중간고사가 끝나고 다시 풀어보고 풀이를 업로드 할 생각이다.