BOJ 16235 : 나무 재테크 (삼성 SW TEST A형)

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/1152 (A형 문제집)

www.acmicpc.net/problem/16235

시뮬레이션 문제는 시키는대로 잘 구현하면 된다.

봄 : 나무의 나이만큼 양분 감소, 나무의 나이 1 증가, 어린 나무부터 양분 획득, 양분 부족시 사망.

여름 : 죽은 나무가 양분으로 나이 / 2 만큼 추가

가을 : 8방향 번식 나이 1의 나무가 생성

겨울 : 양분 추가

문제의 핵심은 나무가 중복될 수 있다는 것이다.

그리고 어린 나무부터 양분을 획득한다 조건에서 정렬이 필요할 것 같다.

무작정 구현했더니, time out이 나오게 되었다.

/* time out */
void spring()
{
	/* 나무를 나이 순으로 정렬 */
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int& treeCount = tcnt[r][c];

			for (int k = 0; k < treeCount - 1; k++)
			{
				for (int t = k + 1; t < treeCount; t++)
				{
					if (tree[r][c][k].age > tree[r][c][t].age)
					{
						TREE tmp = tree[r][c][k];
						tree[r][c][k] = tree[r][c][t];
						tree[r][c][t] = tmp;
					}
				}
			}
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int& treeCount = tcnt[r][c];
			for (int t = 0; t < treeCount; t++)
			{
            	/* 죽은 나무는 pass */
				if (tree[r][c][t].live != 1) continue;
				
                /* 살아있는 나무면 양분 처리 */
				if (tree[r][c][t].age <= energy[r][c])
				{
					energy[r][c] -= tree[r][c][t].age;
					tree[r][c][t].age++;
				}
				else
				{
					tree[r][c][t].live = 0; /* 죽은 나무 표시 */
				}
			}
		}
	}
}

void summer()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int& treeCount = tcnt[r][c];
			for (int t = 0; t < treeCount; t++)
			{
				if (tree[r][c][t].live == 0) /* 죽은 나무면 */
				{
					tree[r][c][t].live = -1; /* 양분이 된 것을 표시 */
					energy[r][c] += (tree[r][c][t].live / 2);
				}
			}
		}
	}
}

첫째로, spring()에서 나무를 정렬하는데 비용이 많이 든다.

둘째, 나무가 죽었는지 살았는지 체크하는 것이 비효율적이다.

따라서 아래와 같은 설계로 바꾸어서 문제를 해결하였다.

1) 덱(deque)을 이용하여 정렬이 필요없도록 만든다. (덱에 관한 연습은 링크를 참고하자.)

2) 살아있는 나무와 죽은 나무를 구분한다.

먼저, 최초로 나무는 중복되지 않으므로, 이미 모두 정렬되어 있다.

그리고 신규로 추가되는 나무는 나이가 가장 어리므로, 현재 나무위치보다 앞으로 정렬된다.

따라서 앞으로 push할 수 있는 덱을 사용하면 정렬을 할 수 있다.

마지막으로, 나무가 양분이 부족하면, 남아있는 모든 나무도 죽게 된다.

즉 spring에서 죽은 나무를 찾으면, 뒤의 (r, c)의 나무도 모두 죽은 나무로 구분하면 된다.

모두 죽은 나무는 양분에 추가하기만 하면 되므로, 다시 for문을 돌 필요없이, spring에서 바로 처리한다.

이러면 죽은 나무를 따로 보관할 필요가 없다.

먼저 선언된 변수를 확인해 보자.

#define MAX (10 + 5)

int N, M, K;
int energy[MAX][MAX];
int A[MAX][MAX];

int tree[MAX][MAX][50000 + 50000];
int front[MAX][MAX];
int back[MAX][MAX];

energy는 양분을 저장하는 배열, A는 S2D2가 추가할 양분이다.

tree는 3차원 배열로 만든다. tree[r][c]에 중복으로 tree가 존재한다.

tree의 (r, c)에 나무가 몇개 있는지는 front와 back을 이용해 알 수 있다.

덱을 이용하므로, 앞으로 push/pop은 front index를 사용하고, 뒤로 push/pop은 back을 사용한다.

덱을 위해 배열의 초기값을 배열의 가운데로 잡는다.

나무가 최대 K = 1000까지 증식하므로 넉넉하게 배열을 10만 정도로 잡았다.

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &A[r][c]);
			energy[r][c] = 5; /* 양분 초기화 */
		}
	}
	
    /* deque index 초기화 */
	for (int r = 1; r <= N; r++) 
		for (int c = 1; c <= N; c++)
			front[r][c] = back[r][c] = 50000;

	for (int i = 0; i < M; i++)
	{
		int x, y, z;

		scanf("%d %d %d", &x, &y, &z);

		int& treeCount = back[x][y];
		tree[x][y][treeCount++] = z;
	}
}

이때, int& treeCount = back[x][y]; 처럼 참조자를 이용하면 2차원 배열 index를 다루기 쉽다.

참조자는 해당 변수의 이름을 빌려오기 때문에, treeCount가 올라가면 back[x][y]가 실제로 올라가게 된다.

이제 spring/summer 코드를 보자.

void spring_summer()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int start = front[r][c];
			int end = back[r][c];

			int& fr = front[r][c];
			int& bk = back[r][c];

			int t;
			for (t = start; t < end; t++) /* 현재 나무를 모두 탐색 */
			{
				if (tree[r][c][t] <= energy[r][c])
				{
					energy[r][c] -= tree[r][c][t];
					tree[r][c][t]++;

					fr++; /* 양분을 먹은 나무는 pop 해서*/
					tree[r][c][bk++] = tree[r][c][t]; /* 다시 뒤로 보낸다 */
				}
				else
					break; /* 양분이 부족하면 break */
				
			}

			for (; t < end; t++) /* 이후 t부터는 모두 죽는다 */
			{
				fr++; /* deque에서 pop */
				energy[r][c] += (tree[r][c][t] / 2); /* 양분 추가 */
			}
		}
	}
}

위의 코드에 start, end와 fr, bk가 필요한 점을 이해해야 한다.

그림으로 이해해보자.

어떤 tree[r][c]에 6개의 나무가 있고 나이 순으로 정렬되어 있다.

모든 tree를 한번씩은 탐색해야하므로 현재의 index는 front와 back으로 받아온다.

하지만 덱이 변화하기 때문에 fr, bk는 참조자를 이용해 변경된 덱의 index를 갱신하고,

start와 end는 spring에서 탐색을 위해서만 사용해야 하기 때문에 그대로 값을 유지한다.

(이때, 덱의 index는 0부터가 아니므로 임의로 5로 잡았다.)

위의 그림은 나무 3개까지 양분을 먹어 나이를 먹고, 덱의 뒤로 push 된 그림이다.

이제 start = 8 (4번째) 나무부터 end = 10 (6번째) 나무까지는 모두 죽는다.

따라서 break로 종료하고, 남은 end까지 양분으로 보낸다.

다음 탐색에서 tree를 볼 필요가 없기 때문에 fr을 이용해 덱에서 pop하기만 하면 된다.

spring과 summer가 종료했음에도 불구하고 나무가 여전히 정렬된 상태가 되었다.

만약에 이때, 주변 나무의 번식으로 인해 tree[r][c]에 나무가 추가된다고 하더라도,

age가 1이기 때문에 정렬은 유지된다.

앞에서 push는 fr을 감소시키면서 넣으면 된다.

autumn 코드를 참고하자.

/* 8방향 탐색을 위한 배열 */
int dr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void autumn()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int start = front[r][c];
			int end = back[r][c];

			for (int t = start; t < end; t++)
			{
				if (tree[r][c][t] % 5 != 0) continue; /* 5의 배수인 경우만 번식 */

				for (int i = 0; i < 8; i++)
				{
					int nr, nc;

					nr = r + dr[i];
					nc = c + dc[i];

					if (nr < 1 || nc < 1 || nr > N || nc > N) continue; /* 경계 조건 */

					int& treeFront = front[nr][nc];

					tree[nr][nc][--treeFront] = 1; /* deque의 앞부분에 push */
				}
			}
		}
	}
}

보통 2차원 배열에서 4방향 탐색을 위해 dr/dc를 만들었었는데, 8방향일 경우에 4개를 더 추가해주면 된다.

문제에 친절하게 8방향을 알려주었으니 배열로 옮기기만 하면 된다.

땅을 벗어나는 칸에 나무가 생기면 안되므로 경계조건을 이용하면 된다.

이제 번식이 가능한 나무와 위치를 알았으므로, 그 위치의 front index를 이용하여 덱의 앞에 push해주자.

겨울 코드는 간단하므로 최종 코드를 참고하면 된다.

#include <stdio.h>

#define MAX (10 + 5)

int N, M, K;
int energy[MAX][MAX];
int A[MAX][MAX];

int tree[MAX][MAX][50000 + 50000];
int front[MAX][MAX];
int back[MAX][MAX];

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &A[r][c]);
			energy[r][c] = 5;
		}
	}
	
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			front[r][c] = back[r][c] = 50000;

	for (int i = 0; i < M; i++)
	{
		int x, y, z;

		scanf("%d %d %d", &x, &y, &z);

		int& treeCount = back[x][y];
		tree[x][y][treeCount++] = z;
	}
}

void spring_summer()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int start = front[r][c];
			int end = back[r][c];

			int& fr = front[r][c];
			int& bk = back[r][c];

			int t;
			for (t = start; t < end; t++)
			{
				if (tree[r][c][t] <= energy[r][c])
				{
					energy[r][c] -= tree[r][c][t];
					tree[r][c][t]++;

					fr++;
					tree[r][c][bk++] = tree[r][c][t];
				}
				else
					break;
				
			}

			for (; t < end; t++)
			{
				fr++;
				energy[r][c] += (tree[r][c][t] / 2);
			}
		}
	}
}

int dr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void autumn()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int start = front[r][c];
			int end = back[r][c];

			for (int t = start; t < end; t++)
			{
				if (tree[r][c][t] % 5 != 0) continue;

				for (int i = 0; i < 8; i++)
				{
					int nr, nc;

					nr = r + dr[i];
					nc = c + dc[i];

					if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

					int& treeFront = front[nr][nc];

					tree[nr][nc][--treeFront] = 1;
				}
			}
		}
	}
}

void winter()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			energy[r][c] += A[r][c];
}


int main(void)
{
	input();

	for (int time = 0; time < K; time++)
	{
		spring_summer();
		autumn();
		winter();
	}

	int ans = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			ans += back[r][c] - front[r][c];

	printf("%d\n", ans);

	return 0;
}

마지막으로 살아있는 나무의 크기는 각 나무 위치의 index의 차이이다. (back - front)

실제 A형에서 초기화를 할 때, 덱의 index를 배열의 가운데로 잡아야 하는 것을 잊지 말자.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 17144 : 미세먼지 안녕! (삼성 SW TEST A형) (0)	2021.03.08
BOJ 16236 : 아기 상어 (삼성 SW TEST A형) (0)	2021.03.06
BOJ 16234 : 인구 이동 (삼성 SW TEST A형) (0)	2021.03.02
BOJ 5373 : 큐빙 (삼성 SW TEST A형) (0)	2021.02.27
BOJ 15686 : 치킨 배달 (삼성 SW TEST A형) (0)	2021.02.25

피로물든딸기의 라이브러리

BOJ 16235 : 나무 재테크 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 16235 : 나무 재테크 (삼성 SW TEST A형)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바