백준 16235 - 나무 재테크

문제링크

• 백준 16235

문제설명

• 시간제한(0.3초)
  • 1초에 가능한 연산양은 O(n)을 기준으로 대략 n이 1억개일 때 가능한 시간이라고 본다.
  • 0.3초는 대략 n이 3천만 정도임을 생각하고 가자
• NxN 크기의 땅에 양분이 있고, 각 칸에는 두개 이상의 나무를 심을 수 있다.
• 나무는 사계절 동안 아래와 같은 시간을 보낸다.
  • 봄
  • 나무가 자신이 위치한 칸에서 나이만큼 양분을 먹고, 나이가 1 증가한다.
  • 같은 칸에 위치한 나무가 여러 개인 경우 나이가 적은 나무부터 양분을 먹는다.
  • 만약 양분이 부족해서 자신의 나이만큼 양분을 먹을 수 없는 나무는 즉시 죽는다.
  • 여름
  • 봄에 죽은 나무가 양분으로 변한다. 각각의 나무의 나이를 2로 나눈 값(소수점 무시)을 각 칸에 더해준다.
  • 가을
  • 나이가 5의 배수인 나무는 번식한다.
  • 번식은 인접한 8개의 칸으로 가능하며, 땅을 벗어나지 않는 칸에 나이가 1인 나무가 생겨난다.
  • 겨울
  • S2D2 라는 로봇이 입력으로 받은 추가하는 양분 A[r][c] 를 각 칸에 추가해준다.
• K년이 지난 후 살아남은 나무의 수를 출력한다.

문제접근(시간초과)

• 나무의 정보를 표현하는 Tree 구조체 (xpos, ypos, age)를 선언한다.
• 봄과 여름은 하나의 함수로 구현한다. 이때, 양분을 나이 순서대로 먹기 위해서 sort 함수를 통해 나이를 기준으로 오름차순 정렬을 해준다.
  • 구조체의 경우 여러 개의 변수를 정렬하는 것과 같으므로, nlog(n)의 시간복잡도를 가지는 sort 함수에 실질적으로는 3nlog(3n)이 들어간 연산량과 같다.
• 위의 이유로 시간초과가 발생했다고 생각했고, 구조체 정렬이 아닌 방법을 생각해보아야 했다.

구현(42% 시간초과)

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

typedef struct _tree {
	int xpos, ypos, age;
} Tree;

int N, M, K;
int A[101][101] = { 0, };
int land[101][101];
vector<Tree> treeList;
int ans = 0; // 살아 있는 나무의 개수
int dx[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dy[8] = { 0, 0, -1, 1, 1, -1, 1, -1 };

void printLand() {
	printf("###################################\n");
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			printf("%d ", land[r][c]);
		}
		printf("\n");
	}
}

// 나이가 어린 순서부터 오름차순 정렬
bool cmpAge(Tree t1, Tree t2) {
	return t1.age < t2.age;
}

void springSummer() {
	int nland[101][101]; // 죽은 나무들의 양분이 더해진 땅의 상태
	vector<Tree> ntreeList;
	memcpy(nland, land, sizeof(land));
	sort(treeList.begin(), treeList.end(), cmpAge);
	for (int i = 0; i < treeList.size(); i++) {
		int x = treeList[i].xpos;
		int y = treeList[i].ypos;
		int age = treeList[i].age;
		if (land[x][y] >= age) {
			land[x][y] -= age;
			nland[x][y] -= age;
			treeList[i].age++;
			ntreeList.push_back(treeList[i]);
		}
		else {
			ans--;
			nland[x][y] += (age / 2); // 죽은 나무는 여름에 양분으로 변함
		}
	}
	memcpy(land, nland, sizeof(nland));
	treeList = ntreeList;
}

void fall() {
	int len = treeList.size();
	for (int i = 0; i < len; i++) {
		if (treeList[i].age % 5 != 0) continue;
		for (int dir = 0; dir < 8; dir++) {
			int nextX = treeList[i].xpos + dx[dir];
			int nextY = treeList[i].ypos + dy[dir];
			if (nextX<1 || nextX>N || nextY<1 || nextY>N) continue;
			Tree ntree;
			ntree.xpos = nextX; ntree.ypos = nextY;
			ntree.age = 1;
			treeList.push_back(ntree);
			ans++;
		}
	}
}

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

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	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]);
			land[r][c] = 5;
		}
	}

	Tree tree;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &tree.xpos, &tree.ypos, &tree.age);
		treeList.push_back(tree);
		ans++;
	}
	for (int i = 0; i < K; i++) {
		springSummer();
		fall();
		winter();
	}
	printf("%d\n", ans);
	return 0;
}

문제접근(Solved)

• vector treeTable[x][y] 형태의 인접그래프를 생성하여 (x,y)에 위치한 나무의 나이를 담도록 한다.
• 위 처럼 나무 데이터를 관리할 경우 int 변수 한가지에 대해서만 정렬이 가능하므로 시간초과가 났던 방법에 비해 연산량을 1/3 정도로 줄일 수 있다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

int N, M, K;
int A[11][11] = { 0, };
int land[11][11];
int lenTable[11][11];
int ans = 0; // 살아 있는 나무의 개수
int dx[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dy[8] = { 0, 0, -1, 1, 1, -1, 1, -1 };
vector<int> treeTable[101][101]; // treeTable[x][y][i] 는 x,y에 위치한 i번째 tree

void springSummer() {
	int nland[11][11]; // 죽은 나무들의 양분이 더해진 땅의 상태
	memcpy(nland, land, sizeof(land));
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			// 나이 순서대로 오름차순 정렬
			vector<int> tmp;
			sort(treeTable[r][c].begin(), treeTable[r][c].end());
			int len = lenTable[r][c];
			for (int i = 0; i < len; i++) {
				if (land[r][c] >= treeTable[r][c][i]) {
					land[r][c] -= treeTable[r][c][i];
					nland[r][c] -= treeTable[r][c][i];
					tmp.push_back(treeTable[r][c][i]+1);
				}
				else {
					ans--;
					nland[r][c] += (treeTable[r][c][i] / 2); // 죽은 나무의 양분
				}
			}
			treeTable[r][c].clear();
			for (auto ele : tmp) {
				treeTable[r][c].push_back(ele);
			}
			lenTable[r][c] = treeTable[r][c].size();
		}
	}
	memcpy(land, nland, sizeof(nland));
}

void fall() {
	int nlenTable[11][11];
	memcpy(nlenTable, lenTable, sizeof(lenTable));
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int len = lenTable[r][c];
			for (int i = 0; i < len; i++) {
				if (treeTable[r][c][i] % 5 != 0) continue;
				for (int dir = 0; dir < 8; dir++) {
					int nextX = r + dx[dir];
					int nextY = c + dy[dir];
					if (nextX<1 || nextX>N || nextY<1 || nextY>N) continue;
					treeTable[nextX][nextY].push_back(1);
					nlenTable[nextX][nextY]++;
					ans++;
				}
			}
		}
	}
	memcpy(lenTable, nlenTable, sizeof(nlenTable));
}

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

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	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]);
			land[r][c] = 5;
		}
	}
	
	memset(lenTable, 0, sizeof(lenTable));
	int x, y, age;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &x, &y, &age);
		treeTable[x][y].push_back(age);
		lenTable[x][y]++;
		ans++;
	}
	
	for (int i = 0; i < K; i++) {
		springSummer();
		fall();
		winter();
	}
	printf("%d\n", ans);
	return 0;
}