[백준]나무재테크
하루를 꼬박 날렸다.
먼저 vector erase 함수는 O(n)이다 안쓰는게 나음 .ㅋ
그리고 객체 없앨 때, 그냥 0을 대입해주고 continue를 해주니까 시간초과가 생긴다.
아마도 루프가 많아지다보면 0자체도 탐색을 해보고 continue를 해주기 때문에 오래걸리나 보다...
그냥 인덱스 자체를 없애거나 다른 공간으로 저장해서 탐색을 시작조차 못하게 해야한다.
clear함수는 생각보다 시간복잡도가 낮은거 같다.
문제를 처음 보자마자 시뮬레이션이라는걸 알았고, 생각보다 쉬울것이라고 생각했지만, 예상치 못한거 에서 시간을 너무
많이 썼다. erase 함수때문에 거의 다 쓴거같다. 지울때 인덱스를 댕겨줘서 생각과 다르게 계속 나이먹은애가 다시
나이를 먹었다. 나이가 어린순으로 먹어야하기때문에 sort를 사용해야 겠다고 생각을 했었다.
그리고 11x11개의 배열형태로 벡터를 저장하는 법을 몰라서 오래걸렸었다.
처음에는 그냥 벡터안에 모든 나무들을 저장해서 코딩했는데, 격자마다 정렬이 필요할 때, 모든것을 정렬해야하기
때문에 격자만의 저장공간이 필요하다고 생각했고, vector<int> map[11][11]을 선언하게 되었다.
문제
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다.
상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
매일 매일 넓은 땅을 보면서 뿌듯한 하루를 보내고 있던 어느 날 이런 생각이 들었다.
나무 재테크를 하자!
나무 재테크란 작은 묘목을 구매해 어느정도 키운 후 팔아서 수익을 얻는 재테크이다. 상도는 나무 재테크로 더 큰 돈을 벌기 위해 M개의 나무를 구매해 땅에 심었다. 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.
이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.
봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M, K가 주어진다.
둘째 줄부터 N개의 줄에 A배열의 값이 주어진다. r번째 줄의 c번째 값은 A[r][c]이다.
다음 M개의 줄에는 상도가 심은 나무의 정보를 나타내는 세 정수 x, y, z가 주어진다. 처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고, 마지막 정수는 그 나무의 나이를 의미한다.
출력
첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.
제한
- 1 ≤ N ≤ 10
- 1 ≤ M ≤ N2
- 1 ≤ K ≤ 1,000
- 1 ≤ A[r][c] ≤ 100
- 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
- 입력으로 주어지는 나무의 위치는 모두 서로 다름
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
int N, M, K;
int A[11][11]; //양분 추가
int map[11][11]; //양분 맵
//vector<int> map(10); //int형을 받는 벡터의 크기가 10이다.(int를 10개받는다)
vector<int> isV[11][11]; //**tree형을 받는 벡터 isV가 11x11배열로 존재한다.
int dr[] = {-1,-1,-1,0,0,1,1,1};
int dc[] = {-1,0,1,-1,1,-1,0,1};
bool InRagne(int r, int c) {
if (r <= 0 || c <= 0 || r > N || c > N) return false;
else return true;
}
bool cmp(int a, int b) {
if (a < b) return true;
else return false;
}
int main()
{
cin >> N >> M >> K; //겨울에 추가되는 양분의 수, 나무의 개수, K년
int answer = 0;
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
cin >> A[i][j]; map[i][j] = 5;
}
for (int i = 0; i < M; i++) {
int R, C, AGE;
cin >> R >> C >> AGE;
isV[R][C].push_back(AGE);
}
for (int i = 0; i < K; i++) { //K년
//봄&여름(핵심부분..)
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (isV[r][c].size() == 0) continue;
vector<int> t1; //산거
int aa = 0;
sort(isV[r][c].begin(), isV[r][c].end(), cmp);
for (int k = 0; k < isV[r][c].size(); k++) {
if (map[r][c] >= isV[r][c][k]) { //양분 O,인덱스로 접근
map[r][c] -= isV[r][c][k];
t1.push_back(isV[r][c][k]+1); //산거 저장.
}
else {
//양분 X
aa += int(isV[r][c][k] / 2);(**아이디어)
}
}
isV[r][c].clear(); //지우고(년도마다 갱신해야되니까)
for (int aa : t1) isV[r][c].push_back(aa);
map[r][c] += aa; //죽은 시체 양분보충
}
}
//가을
for (int r = 1; r <= N; r ++ ) {
for (int c = 1; c <= N; c++) {
if (isV[r][c].size() == 0) continue;
for (int m = 0; m < isV[r][c].size(); m++) {
if (isV[r][c][m] % 5 != 0) continue;
for (int k = 0; k < 8; k++) {
int xx = r + dr[k];
int yy = c + dc[k];
if (InRagne(xx, yy) == false) continue;
isV[xx][yy].push_back(1);
}
}
}
}
//겨울
for (int r = 1; r <= N; r++) for (int c = 1; c <= N; c++) map[r][c] += A[r][c];
//Show();
}
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
answer += isV[r][c].size();
}
}
cout << answer << endl;
return 0;
}
|
cs |