카카오 코드 페스티벌 2017 본선 해설(Ongoing)
* 2017 카카오코드 본선
이 글은 카카오가 제시한 해설과 다소 다를 수 있습니다.
카카오 기술 공식 블로그에서 에디토리얼을 작성하였으니 참고해주세요
URL : http://tech.kakao.com/2017/09/14/code-festival-round-2/
1. 단체 사진 찍기 [ 분류 - Brute force/ Permutation ]
전체 경우의 수를 생각해보면 8!밖에 되지 않고, 조건의 수가 최대 100개이기 때문에 완전 탐색으로 답을 도출해낼 수 있다.
next_permutation이나 기타 완탐 구조를 통해 답을 도출해내자.
#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의 판이 존재함으로 충분히 시간내에 답을 낼 수 있다.
#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)이 된다.
#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이상이면 채운다.
#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에서 우하단 영역을 밟았다면 바로 종료하도록 한다.
#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)