카카오 코드 페스티벌 2017 본선 해설(Ongoing)

* 2017 카카오코드 본선

이 글은 카카오가 제시한 해설과 다소 다를 수 있습니다.

카카오 기술 공식 블로그에서 에디토리얼을 작성하였으니 참고해주세요

      URL : http://tech.kakao.com/2017/09/14/code-festival-round-2/

1. 단체 사진 찍기 [ 분류 - Brute force/ Permutation ] 

  전체 경우의 수를 생각해보면 8!밖에 되지 않고, 조건의 수가  최대 100개이기 때문에 완전 탐색으로 답을 도출해낼 수 있다.

  next_permutation이나 기타 완탐 구조를 통해 답을 도출해내자.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <string> #include <vector> #include <algorithm> #include <map> using namespace std; struct _d { int a,b,cnt, code; }; int abs_v(int a) { return a < 0 ? -a : a; }   int solution(int n, vector<string> data) {     char friends[] = "ACFJMNRT";     int answer = 0,a,b,code,cnt=0,i, pos[8],can,d;     map<char, int> comp;     vector<_d> pool;     vector<int> p;     for(i=0;i<8;i++) {         comp.insert({friends[i], i});         p.push_back(i);     }       for(string& s : data){         a = comp[s[0]], b = comp[s[2]];         cnt = s[4]-'0', code = s[3];         pool.push_back(_d{a,b,cnt,code});     }       do {         for(i=0;i<8;i++) pos[p[i]] = i;         can = 1;         for(_d& e : pool){             d = abs_v(pos[e.a]-pos[e.b]) - 1;             switch(e.code){             case '>': can &= (d > e.cnt); break;             case '<': can &= (d < e.cnt); break;             case '=': can &= (d == e.cnt); break;             }         }         answer += can;     }while(next_permutation(p.begin(), p.end()));     return answer; }

2. 리틀 프렌즈 사천성 [분류 - BFS/ DFS/ 구현] 

  단 한 번만 꺾을 수 있기 때문에 BFS를 돌며 제한을 두면 간단하다. 내가 짠 소스는 한 번뿐만 아니라 여러번도 가능하긴하다.

  pair의 최대수는 26개, 그리고 100x100의 판이 존재함으로 충분히 시간내에 답을 낼 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <string> #include <vector> #include <queue> #include <cstring> #include <set> using namespace std; struct _d { char c; int y, x; }; struct _q { int y, x, d; }; bool operator<(const _d& a, const _d& b) {     return a.c < b.c; } string solution(int m, int n, vector<string> board) {     string answer = "";     int i, j, bef, aft, dy[] = { 0,1,0,-1 }, dx[] = { 1,0,-1,0 }, matched, vi[100][100][4], chk[26] = {};     queue<_q> q;     set<_d> list;     for (i = 0; i < m; i++) for (j = 0; j < n; j++)         if ('A' <= board[i][j] && board[i][j] <= 'Z') {             list.insert(_d{ board[i][j],i,j });             chk[board[i][j] - 'A'] = 1;         }       do {         bef = (int)list.size();         for (auto it = list.begin(); it != list.end();it++) {             memset(vi, 0x7F, sizeof vi);             while (!q.empty()) q.pop();               for (i = 0; i<4; i++) {                 vi[it->y][it->x][i] = 0;                 q.push(_q{ it->y, it->x, i });             }             matched = 0;             while (!q.empty() && !matched) {                 _q u = q.front(); q.pop();                 for (i = 0; i<4; i++) {                     int ty = u.y + dy[i], tx = u.x + dx[i], used = i != u.d;                     if (0 <= ty && ty < m && 0 <= tx && tx < n && vi[u.y][u.x][u.d] + used < 2 && vi[ty][tx][i] > vi[u.y][u.x][u.d] + used && board[ty][tx] != '*' && (board[ty][tx] == '.' || board[ty][tx] == it->c)) {                         vi[ty][tx][i] = vi[u.y][u.x][u.d] + used;                         q.push(_q{ ty,tx,i });                         if (board[ty][tx] == it->c) {                             matched = 1;                             board[it->y][it->x] = board[ty][tx] = '.';                         }                     }                 }             }             if (matched) {                 answer += it->c;                 list.erase(it);                 break;             }         }         aft = (int)list.size();     } while (bef != aft);     if (!list.empty()) answer = "IMPOSSIBLE";     return answer; }

3. GPS [분류 - Dynamic programming ] 

  gps_log의 현재 위치 pos에 대해 현재를 무슨 값으로 바꿔야 하는지에 따라 다음이 달라진다.

  또한 pos에 대해 u의 값으로 "교체"했다면 그 다음의 수순으로 넘어갈 때 최소값은 정해져 있다. 이는 곧 각 gps_log의 위치마다 독립적이라는 뜻이며, 부분 문제가 반드시 존재함을 의미한다.

  즉, pos에 u를 두었다면 pos+1부터는 부문제가 된다.

  dp구성은 다음과 같다. dp[pos][u]에 대해 gps_log에서의 pos에서 u로 가기 위한 수정 수의 최소값.

  따라서 답은 dp[k-1][gps_log의 마지막 정점]을 도출해내면 되며, 수정할 수 없는 경우에는 매우 큰값을 가지게 된다. 따라서 결과적으로 시간복잡도는 O(KNM)이 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <vector> #include <cstring> using namespace std; int min_v(int a, int b){ return a < b ? a : b; } const int INF = 0x3F3F3F3F;   int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {     int answer = 0, u, v, i,j;     vector<vector<int>> adj(n);     int dp[100][200], adjA[200][200]={};           for(vector<int>& e : edge_list){         u = e[0], v = e[1];         u--, v--;         adj[u].push_back(v);         adj[v].push_back(u);         adjA[u][v] = adjA[v][u] = 1;     }     for(i=0;i<n;i++) {         adj[i].push_back(i);         adjA[i][i] = 1;     }     memset(dp, 0x3F, sizeof dp);     for(i=0;i<k;i++) gps_log[i]--;     dp[0][gps_log[0]] = 0;     for(i=1;i<k;i++) {         for(j=0;j<n;j++)             if(dp[i-1][j] != INF){                 for(int& v : adj[j])                     dp[i][v] = min_v(dp[i][v], dp[i-1][j] + (v != gps_log[i]));             }     }     answer = dp[k-1][gps_log[k-1]];     return answer == INF ? -1 : answer; }

4. 몸짱 트레이너 라이언의 고민 [ 분류 - Brute force ] 

가지치기를 매우 정교하게 해야하는 문제다. 모든 구간을 백트랙킹으로 구하게 되면 시간초과가 가볍게 나므로 명확한 경우를 따로 처리하고, 필요한 경우를 수학적 접근 방식을 택해야 한다. 내가 사용한 방식은 전제 및 증명으로 Greedy하게 접근했다.

먼저 겹치는 사람의 최대값을 가져와야한다. 이 최대값에 대해 배치할 때 가장 멀리 배치할 수 있는 값을 최대화시키는 것이기 때문에 거리가 1, 2, ..., 2*(N-1)일 때 사람 배치 수를 구한다. 그리고 순회하며 가능한 거리를 찾으면 그 값을 반환하는 식으로 구현하면 된다. 다음으로 그 사람 배치 수를 구하는 방식을 설명한다.

1. 거리가 1인 경우와 2인 경우

거리 1 : 거리가 1일 때 최대 사람 수용인원은 N*N이 된다.

거리 2 : 거리가 2일 때 최대 사람 수용인원은 N*N/2 + N%2가 된다. 체크 무늬를 생각하면 쉽다. 또한 짝홀 경우를 처리해준다.

2. 거리가 3 이상인 경우

[전제 1] 거리 d에 대해 최대한 사람을 배치할 때, 첫 행은 반드시 사용된다.

[전제 1 증명]

첫 행을 사용하는 경우 사용할 수 있는 넓이는 N*N, 사용하지 않는 경우엔 N*(N-1)이다. 만약 N*(N-1)이 최대 수용인원이 X라면 N*N을 사용할 때 최대 수용인원은 X보다 크거나 같으므로 첫 행을 반드시 사용하는 것이 이득이다.

전제 1에 의해 첫 행을 반드시 사용해야 하므로 첫 행의 열 시작 위치를 결정하고, 밀집된 그래프를 그린다. 이중 for문으로 이전에 현재 사람으로 채우려고하는 cell이 이전에 채운 사람들과의 거리가 d미만이라면 채우지 않고, d이상이면 채운다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include<cstdio> #include<vector> #include<set> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; const int MAX_D = 22; set<pair<int, int>> delta[11]; int manhattan(int& x1, int& y1, int& x2, int& y2) {     return abs(x1 - x2) + abs(y1 - y2); } int vi[10][10]; bool border(int& n, int ty, int tx) { return 0 <= ty && ty < n && 0 <= tx && tx < n; } bool chk(int& n, int& d, int ty, int tx) {     if(border(n,ty,tx) && !vi[ty][tx]) {         int can = 1, i, j;         for(i=-d+1;i<d;i++) for(j=-d+1;j<d;j++) if(abs(i)+abs(j) < d && border(n, ty+i, tx+j))             can &= !vi[ty+i][tx+j];         return can;     }     return 0; } int solution(int n, int m, vector<vector<int>> timetable) {     int answer = 0, maxi = 0, acc[1321] = {}, t1, t2, i, j, occupied[MAX_D], d, sx, cy, cx, can, cnt;     for (i = 0; i < m; i++) {         t1 = timetable[i][0], t2 = timetable[i][1];         for (j = t1; j <= t2; j++) {             acc[j] += 1;             maxi = maxi > acc[j] ? maxi : acc[j];         }     }       occupied[0] = 1e9;     occupied[1] = n*n;     occupied[2] = n * n / 2 + n % 2;     for (d = 3; d<MAX_D; d++) {         occupied[d] = 0;         for (sx = 0; sx<n; sx++) {             memset(vi, 0, sizeof vi);             cy = 0, cx = sx;             do {                 if(chk(n,d,cy,cx))                     vi[cy][cx] = 1;                 cx++;                 if(cx == n) cy++, cx = 0;             } while (cy < n);             cnt = 0;             for (i = 0; i<n; i++) for (j = 0; j<n; j++)                 cnt += vi[i][j];             occupied[d] = max(occupied[d], cnt);         }     }     for (i = MAX_D - 1; i>0; i--) if (occupied[i] < maxi && maxi <= occupied[i - 1]) {         answer = i - 1;         break;     }       return answer = maxi == 1 ? 0 : answer; }

5. 튜브의 소개팅 [분류 - BFS/ Dynamic programming ] 

  솔루션은 꽤 심플하다. k번의 이동회수가 고정적으로 주어졌을 때, 갈 수 있는 영역에 대해 처리해준다고 생각해보자.

  이 문제의 경우 k-1번째에서 k번째로 거리를 이동함을 알 수 있고, k번째 밟은 영역에서 k-1번째로 다시금 밟을 수 없다.(비효율적이기 때문)

  따라서 이 문제 역시 부분문제가 존재하며, step by step으로 진행한다.

  BFS를 통해 하나씩 하나씩 진전하는 소스로 구성하여, K번째 발걸음이 K-1번째의 발걸음을 참조하도록 소스를 구성하면 된다. 마지막으로 최소 발걸음으로 가야하기 때문에 특정 값 k에서 우하단 영역을 밟았다면 바로 종료하도록 한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <vector> #include <queue> #include <cstring> using namespace std; struct _d{ int y,x;}; vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {     int move_distance = 0;     int sum_of_talk_time = 0;     int dy[]={0,0,1,-1},dx[]={1,-1,0,0},i,j,k;     unsigned int dp[50][50][2501];     memset(dp, 0xFF, sizeof dp);     queue<_d> q;     dp[0][0][0] = 0;     q.push(_d{0,0});     for(k=1;k<m*n;k++) {         int qsize = (int)q.size();         while(qsize--){             _d u = q.front(); q.pop();             for(i=0;i<4;i++) {                 int ty = u.y + dy[i], tx = u.x + dx[i];                 if(0 <=ty && ty < m && 0 <= tx && tx < n && time_map[ty][tx] != -1){                     if(dp[u.y][u.x][k-1] + time_map[ty][tx] <= s && dp[ty][tx][k] > dp[u.y][u.x][k-1] + time_map[ty][tx]) {                         dp[ty][tx][k] = dp[u.y][u.x][k-1] + time_map[ty][tx];                         q.push(_d{ty,tx});                     }                 }             }         }         if(dp[m-1][n-1][k] != (unsigned int)(0xFFFFFFFF)) {             move_distance = k;             sum_of_talk_time = dp[m-1][n-1][k];             break;         }     }           vector<int> answer(2);     answer[0] = move_distance;     answer[1] = sum_of_talk_time;                 return answer; }

6. 스마트한 프로도(TODO) 

7. IU와 콘의 보드게임(TODO) 

8. 네오의 귀걸이(TODO)