2018 ACM-ICPC Seoul Regional

2일에 ACM-ICPC 예비소집으로 참가를 했습니다.

세종대에서 진행을 했었는데 대학교 자체가 굉장히 이뻤습니다 ㅋㅋ.

등록을 하면서 티셔츠랑 이름표등을 받고 B홀로 입장을 했는데 많은 사람들이 와있었습니다. 

대회장소에 입장할때부터 대회가 실감이 났던거같습니다.
본선에는 이 장소에서 사진을 찍을 수 없기 때문에 사진을 호다닥 찍었습니다. 

예비소집이 끝나고 나서는 팀원들과 저녁을 먹으러 갔습니다.
하남돼지는 고기를 직원이 직접 구워주기도 해서 편하게 집어먹었습니다. 
가격은 학생이 가기엔 좀 부담스럽긴 한것같습니다




본 대회는 3일 10:05분에 카운트 다운과 함께 대회가 시작되었습니다.
앞에서부터 쭈욱 쉬운문제를 찾고있었는데 D번문제가 표와 테케만으로 
단순한 구현문제임을 알아차렸습니다.
바로 구현을 시작했는데 조건을 하나 안쳐서 한번 틀렸습니다 ㅠㅠ..

그리고 대회시작한지 2시간가량은 깨작 깨작밖에 못한것 같습니다.
저희팀만 그런것이 아니고 스코어보드로도 그런 정황을 느꼈는데 그 때 K번을 접하게되었습니다.
K번을 보고 "그 알고리즘"을 사용할 수 있겠구나 하고 불꽃코딩을 했습니다.
근데 어디서 무한루프가 발생해서 디버깅을 한참동안 하는 고생을 했는데
컴파일러를 g++로 하고 auto 키워드를 사용해서 발생한 문제였습니다 ㅠㅠ...
수정하고 제출해서 바로 맞췄는데 남은시간은 약 2시간....

남은 시간동안에 A번과 F번을 시도해봤는데 두 마리 토끼를 잡다가 둘다 못잡은것 같습니다.
많은 팀들이 L번을 풀었고 저희팀은 시도를 그렇게 하지 않았는데 좀 아쉬웠던것 같습니다.

등수를 먼저 알려주는 노잼 시상식을 보고 팀원+지인들과 밥을 먹었습니다.
이전부터 출장뷔페가 맛이없다는 소문을 들었었는데 너무 맛있었던것 같습니다
결과는 좀 아쉽지만 문제도 좋았던것 같고 많은 지인들과도 만날 수 있었던 재밌는 경험이였습니다.
처음이자 마지막 ICPC라는게 너무 아쉽긴 합니다 ㅠㅠ

+기념품
맘에 듭니다 ㅎㅎ

2018 삼성 S/W 역량 테스트 기출문제

16234 인구이동 https://www.acmicpc.net/problem/16234
16235 나무 재테크 https://www.acmicpc.net/problem/16235
16236 아기상어 https://www.acmicpc.net/problem/16236

삼성 코딩 테스트 대부분은 bfs, dfs, 구현, 완전탐색 정도의 문제들이 많이 출제된다.

이번 2018 하반기 삼성 역량 테스트는 단순한 구현을 하면 시간초과가 나는 문제가 출제되었다.
이 포스트에서는 이러한 문제의 풀이를 다뤄보겠다.


1. 인구이동
- NxN의 땅이 주어진다.

- 각각의 땅에는 나라가 하나씩 존재하며 사람들이 살고있고 상하좌우로 인접한 두 나라의 인구 차이가
  L명이상 R명 이하라면 국경선을 연다.

- 열 수 있는 국경선을 모두 열었다면 인구이동을 시작한다.

- 국경선을 열어 다른나라로 이동할 수 있으면 '연합'이라 칭하고 '연합'을 이루는 각 칸의 개수는 
  (연합의 인구수)/(연합을 이루는 칸의 개수)가 된다.

- 인구이동이 몇번 발생하는지 구하는 문제이다.









disjoint set 자료구조 (union find)를 사용하면 '연합'을 결성하는 문제를 쉽게 해결할 수 있다.
'연합'을 결성하고 각 칸의 개수를 구한 후 반복하면 이 문제를 풀 수 있다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 55; int n, l, r; int dy[] = { -1,0,0,1 }; int dx[] = { 0,1,-1,0 }; int arr[MAXN][MAXN]; int par[2515]; int sze[2515]; int sum[2515]; int find(int x) {     if (par[x] == x) return x;     return par[x] = find(par[x]); } void merge(int u, int v) {     u = find(u); v = find(v);     if (u == v) return;     if (sze[u] > sze[v]) swap(u, v);     sze[v] += sze[u];     par[u] = v; } bool ismove() {     for (int i = 0; i < n*n; i++) par[i] = i, sze[i] = 1, sum[i] = 0;     bool ret = false;     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {         int u = i * n + j;         for (int k = 0; k < 4; k++) {             int ny = i + dy[k], nx = j + dx[k];             if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;             int diff = abs(arr[i][j] - arr[ny][nx]);             if (diff >= l && diff <= r) {                 int v = ny * n + nx;                 merge(u, v);                 ret = true;             }         }     }     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {         int idx = i * n + j;         sum[find(idx)] += arr[i][j];     }     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {         int idx = i * n + j;         int f = find(idx);         arr[i][j] = sum[f] / sze[f];     }     return ret; } int main() {     int ans = 0;     scanf("%d%d%d", &n, &l, &r);     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]);     while (ismove()) ans++;     printf("%d", ans);     return 0; } Colored by Color Scripter

cs

2. 나무 재테크
- NxN의 땅이 주어지며 모든 땅에는 양분이 5만큼 들어있다.

- 현재는 M개의 나무가 땅에 존재한다. 

- 봄에는 나무가 자신의 나이만큼 땅에 있는 양분을 섭취하고 나이가 1증가한다.
 나이가 어린 나무부터 양분을 먹으며 양분이 부족해 섭취하지 못하는 나무는 죽는다.

- 여름에는 봄에 죽은 나무가 나이를 2로 나눈 값으로 양분이 된다.

- 가을에는 나이가 5의 배수인 나무들이 인접한 8개의 방향으로 나이가 1인 나무들을 만들어 낸다.

- 겨울에는 A[r][c]만큼 각 땅에 양분을 추가한다.

- K년이 지난 후 살아있는 나무의 수를 구하는 문제이다.




모든 나무들을 vector형태로 저장하는 구현은 시간초과가 날 가능성이 있다.
현재 위치(y, x) 에 나이가 z인 나무들을 저장하는 save[y][x][turn][z]를 만들어 나무들을 관리해주었다.
(turn은 나이가 1살 증가하는 나무들과 죽는 나무들을 관리하기위해 만듬)

봄,여름,가을,겨울 순으로 주어진 조건대로 구현을 해주면 된다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 11; int n, m, k, type = 0; int arr[MAXN][MAXN], Plus[MAXN][MAXN]; int save[MAXN][MAXN][2][10001]; int mn[MAXN][MAXN], mx[MAXN][MAXN];   int dy[] = { -1,0,0,1,1,1,-1,-1 }; int dx[] = { 0,1,-1,0,1,-1,1,-1 }; int main() {     scanf("%d%d%d", &n, &m, &k);     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &Plus[i][j]), arr[i][j] = 5;     for (int i = 0; i < m; i++) {         int x, y, z;         scanf("%d%d%d", &y, &x, &z); x--; y--;         save[y][x][type][z]++;         mx[y][x] = max(mx[y][x], z);     }     while (k--) {         // 봄, 여름         int nxt = 1 - type;         for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {             bool flag = false;             int tmp_mx = -1e9, tmp_mn = 1e9;             for (int year = mn[i][j]; year <= mx[i][j]; year++) {                 if (!save[i][j][type][year]) continue;                 if (flag) {                     arr[i][j] += (save[i][j][type][year] * (year / 2));        // 나무 죽음                 }                 else {                     tmp_mn = min(tmp_mn, year);                     tmp_mx = max(tmp_mx, year + 1);                     if (save[i][j][type][year] * year > arr[i][j]) {                         int spare = min(save[i][j][type][year], arr[i][j] / year);        // 남아있는 나무 1살 먹음                         arr[i][j] -= spare * year;                         save[i][j][nxt][year + 1] += spare;                         arr[i][j] += ((save[i][j][type][year] - spare) * (year / 2));        // 나무 죽음                         flag = true;                     }                     else {                         arr[i][j] -= save[i][j][type][year] * year;                        // 남아있는 나무 1살 먹음                         save[i][j][nxt][year + 1] += save[i][j][type][year];                     }                 }                 save[i][j][type][year] = 0;             }             mn[i][j] = tmp_mn;             mx[i][j] = tmp_mx;         }           // 가을         type = nxt;         for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {             for (int year = 5; year <= mx[i][j]; year += 5) {                 if (!save[i][j][type][year]) continue;                 for (int t = 0; t < 8; t++) {                     int ny = i + dy[t], nx = j + dx[t];                     if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;                     save[ny][nx][type][1] += save[i][j][type][year];                     mn[ny][nx] = 1;                     mx[ny][nx] = max(mx[ny][nx], 1);                 }             }         }           // 겨울         for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) arr[i][j] += Plus[i][j];     }       int ans = 0;     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {         for (int year = mn[i][j]; year <= mx[i][j]; year++) {             ans += save[i][j][type][year];         }     }     printf("%d", ans);     return 0; } Colored by Color Scripter

cs

3. 아기상어
- NxN의 땅이 주어지며 물고기와 크기가 2인 아기상어가 존재한다.

- 아기상어는 자신의 크기보다 큰 물고기가 있는곳은 가지 못한다.

- 아기상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

- 아래와 같은 방법을 반복한다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

- 아기상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1증가한다.

- 아기상어가 물고기를 잡아먹을 수 있는 시간을 구하는 문제이다.

bfs로 아기상어가 먹을 수 있는 물고기의 존재여부와 위치를 구한 후 조건대로 크기를 키운 후 

물고기를 먹을 수 없을 때 까지 반복하면 문제를 풀 수 있다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 22; int n, sy, sx, sze = 2; int arr[MAXN][MAXN]; bool visit[MAXN][MAXN]; int dy[] = { -1,0,0,1 }; int dx[] = { 0,1,-1,0 }; pair<int,int> bfs(int iy, int ix) {     memset(visit, 0, sizeof visit);     queue<int> q;     q.push(iy*n + ix);     visit[iy][ix] = true;       int dist = 0;     vector<pair<int, int>> v;     while (!q.empty()) {         int z = q.size();         for (int s = 0; s < z; s++) {             int y = q.front() / n, x = q.front() % n;             q.pop();               for (int i = 0; i < 4; i++) {                 int ny = y + dy[i], nx = x + dx[i];                 if (ny < 0 || ny >= n || nx < 0 || nx >= n || visit[ny][nx] || arr[ny][nx] > sze) continue;                 visit[ny][nx] = true;                 if (arr[ny][nx] > 0 && arr[ny][nx] < sze) v.push_back({ dist + 1,ny*n + nx });                 q.push(ny*n + nx);             }         }         dist++;     }     sort(v.begin(), v.end());     if (v.empty()) return {-1,-1};     return v[0]; } int main() {     scanf("%d", &n);     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {         scanf("%d", &arr[i][j]);         if (arr[i][j] == 9) sy = i, sx = j, arr[i][j] = 0;     }       int eat = 0, ans = 0;     while (1) {         auto g = bfs(sy, sx);         if (g.first == -1) break;         sy = g.second / n, sx = g.second % n;         ans += g.first;         arr[sy][sx] = 0;         if (++eat == sze) {             eat = 0;             ++sze;         }     }     printf("%d", ans);     return 0; } Colored by Color Scripter

cs