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;
}
| 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;
}
| 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;
}
| cs |
