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

S/W Poster

학교공부에 치여 살다보니 알고리즘 문제 풀이를 안한지 3달정도가 지났는 데 학교 엘레베이터에 위와 같은 코테 포스터가 붙여진 것을 보았다.
실력 테스트도 해보고 상금도 노릴겸 해서 겸사겸사 신청을 했다.

대회 시상관련은 본선 진출시 기념품과, 대상 1명 50만원, 우수상 7명 30만원, 장려상 15명 10만원이었다.

사실 예선 통과후 본선에 들면 40명중 절반 이상인 23명안에만 들어도 10만원의 상금을 준다는 것을 보고 10만원을 목표로 신청했다.

예선전2020. 10. 07. 수요일에 18:00 ~ 22:00 까지 온라인을 통해 이루어졌다.
나는 수요일 당일 20시까지 수업이 있어 늦게 시작해야했는데, 수업이 조금 일찍 끝나 20시쯤 부터 문제풀이를 시작했다.

시간이 두시간 밖에 없어 떨어질 생각하고 편하게 테스트 봤다.



📌 예선전 문제


1️⃣ 다음 순열


문제 보기


1번 문제는 다음 순서로 올 순열을 출력하는 쉬운 문제여서 next_permutation 함수를 이용하여 쉽게 풀 수 있었다.


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

using namespace std;

int main()
{
    int N,K;
    cin >> N >> K;
    vector<vector<int>> arr(K,vector<int>(N,0));

    for(int i=0; i <K;i++){
        for(int j=0; j < N; j++){
            cin >> arr[i][j];
        }
    }
    for(int i=0; i < K; i++){
        next_permutation(arr[i].begin(),arr[i].end());
    }
    for(int i=0; i < K; i++){
        for(int j=0; j < N ; j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
}



2️⃣ 베스트 앨범


문제 보기


2번 문제는 블로그에도 한번 포스팅했던 프로그래머스베스트 앨범 문제였다.

프로그래머스에서도 풀어보고 포스팅하면서 다시 풀어보고 여러번 풀어봤던 문제였기에, map(hash table)을 이용하여 값을 더해주고 value를 기준으로 내림차순 정렬하여 값을 출력하는 방법으로 쉽게 풀이 했다.

c++ 에서 map을 key가 아닌 value로 정렬을 쉽게 하는 방법은 pair을 갖는 vector로 옮겨 vector로 정렬 하는 방법이 있습니다.


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

using namespace std;

bool compare(pair<int,int> a,pair<int,int> b){
    return a.first > b.first;
}
bool compare_map_value(pair<string,int> a,pair<string,int> b){
    return a.second > b.second;
}

int main() {
  	int N; cin >> N;
    vector<string> genres(N,"");
  	vector<int> plays(N,0);
  	for(int i=0; i < N; i++){
      	cin >> genres[i] >> plays[i];
    }

    unordered_map<string,vector<pair<int,int>>> genre_playlist;
    unordered_map<string,int> genre_play_cnt;
    vector<pair<string,int>> genre_play_cnt_v;

    for(int i=0; i < genres.size(); i++){
        genre_playlist[genres[i]].push_back(make_pair(plays[i],i));
        genre_play_cnt[genres[i]]+=plays[i];
    }
    for(auto &k : genre_playlist){
        sort(k.second.begin(),k.second.end(),compare);
    }
    genre_play_cnt_v.assign(genre_play_cnt.begin(),genre_play_cnt.end());
    sort(genre_play_cnt_v.begin(),genre_play_cnt_v.end(),compare_map_value);

    for(int i=0; i < genre_play_cnt_v.size(); i++){
        string genre_name = genre_play_cnt_v[i].first;
        for(int j=0; (j < genre_playlist[genre_name].size() ) && (j < 2) ; j++){
            cout << genre_playlist[genre_name][j].second <<endl;
        }
    }
}



3️⃣ 등교길


문제 보기


문제 설명 마지막에 친절하게도 hintdp를 이용하여 풀라고 설명이 되어 있어 dp를 이용해 풀었으며, 중학교 수학문제의 확률과 통계에서 최단 거리 경우의 수 문제를 풀듯이 풀었다.


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

using namespace std;

int main(){
    int m,n; cin >> m >> n;
    int N; cin >> N;
    vector<vector<int>> puddles(N,vector<int>(2,0));

    for(int i=0; i < N; i++){
        for(int j=0; j < 2; j++){
            cin >> puddles[i][j];
        }
    }

    vector<vector<bool>> map(n+1,vector<bool>(m+1,false));
    vector<vector<int>> dis(n+1,vector<int>(m+1,0));

    for(auto puddle : puddles)
        map[puddle[1]][puddle[0]] = true;

    dis[0][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m ; j++){
            if(!map[i][j])
                dis[i][j] = (dis[i-1][j] %1000000007 + dis[i][j-1] % 1000000007) % 1000000007;
            else dis[i][j] = 0;
        }
    }
    cout << dis[n][m] % 1000000007;
}



4️⃣ 토큰 기계


문제 보기


이때 시간이 40분도 채 남지 않았는 데, 문제는 3문제가 남아 있어 선택을 해야하는 상황이 왔었다.

그래서 남은 세 문제중 한 문제만 더 풀자 하고 가장 통과율이 높은 마지막 문제선택했기 때문에, 4,5 번은 문제는 보지도 못했다..



5️⃣ 사회적 거리두기 1


문제 보기



6️⃣ 마우스 미로


문제 보기


시간안에 한두개 케이스라도 통과해보자는 마음으로 문제 풀이를 시작 했고, 최단 경로가 있는지 없는지 검사만 하는것이 아니라 최단 경로까지의 길을 x로 출력해야 해서 bfs로는 최단 경로에 포함되지 않은 길은 x표시를 제외하려고 하면 복잡해질 것 같아 dfs로 풀이를 시작했다.

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

을 이용했으며, 제일 끝 쪽 벽이 막혀있는 것이 아니라 다음 벽으로 이어져 있기 때문에 현재 위치에서 dir값총 배열 길이(x축이면 C,y축이면 R)을 더하고 배열 길이만큼 나눈 나머지를 이용하여 dfs를 풀이했다.

int next_x = (x + dir[i][0] + C) % C;
int next_y = (y + dir[i][1] + R) % R;

하지만, 마음이 급했는 지 ===로 잘못쓰는 등 잔실수들 때문에 버그 고치느라 타임아웃되어 제출을 하지 못하고 예선이 끝났다.


버그 고친 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int R, C;
int M_x, M_y;
int D_x, D_y;
bool arrive = false;
vector<vector<char>> answer;

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(vector<vector<char>> map, vector<vector<bool>> &visit, int x, int y)
{
    if (y == D_y && x == D_x){
        arrive = true;
        answer = map;
        return;
    }
    if (map[y][x] != 'M')
        map[y][x] = 'x';
    visit[y][x] = true;
    for (int i = 0; i < 4; i++){
        int next_x = (x + dir[i][0] + C) % C;
        int next_y = (y + dir[i][1] + R) % R;

        if ((map[next_y][next_x] == '.' || map[next_y][next_x] == 'D') && visit[next_y][next_x] == false){
            visit[next_y][next_x] == true;
            dfs(map, visit, next_x, next_y);
        }
    }
    return;
}

int main()
{
    cin >> R >> C;
    vector<vector<char>> arr(R, vector<char>(C, '0'));
    vector<vector<bool>> visit(R, vector<bool>(C, false));
    string str;

    for (int i = 0; i < R; i++){
        int j = 0;
        cin >> str;
        for (auto c : str){
            arr[i][j] = c;
            if (arr[i][j] == 'M'){
                M_x = j;
                M_y = i;
            }
            if (arr[i][j] == 'D'){
                D_x = j;
                D_y = i;
            }
            j++;
        }
    }

    dfs(arr, visit, M_x, M_y);
    if (arrive){
        cout << "YES" << endl;
        for (int i = 0; i < answer.size(); i++){
            for (int j = 0; j < answer[i].size(); j++){
                cout << answer[i][j];
            }
            cout << endl;
        }
    }
    else{
        cout << "NO";
    }
    return 0;
}


종료후에 제출하여 코드를 확인해보니 위의 코드도 완벽히 통과는 못하고 마지막 두개의 케이스메모리 초과로 실패가 뜨는 것을 확인했다.


부분점수



🎉 예선전 후기


10시에 칼같이 시험이 끝나고 바로 점수가 집계되었는데, 총 점 120점 만점에 40점으로 16등으로 통과했다.
(생각도 못했는데 이게 웬 걸)

늦게 시작했지만 예선 통과해서 좋았고, 1등108점으로 19학번이 한것을 보고 대단하다는 생각과 동시에 자괴감이 들었으며, 총원과 점수들을 보니 생각보다 많은 사람이 참여를 안했구나 싶었다.


본선 후기는 다음글에 이어서 포스팅 할 예정이다.