글 읽기 - 공손히 부탁드립니다.. 2주째 시간초과 제발 도와주세요

bongbbi 3년 전 0

지금 2주째 나무랑 씨름중인데, 제출하자마자 바로 시간초과 뜨고있습니다....

정말 절실하게 도움이 필요합니다.

제가 짠 소스에서 어떤부부분을 고쳐야 시간 초과를 해결할 수 있는지 궁금합니다.

만약 더 줄일 수 없으면 아예 다른 방법으로 바꿔야하는지도 여쭤보고 싶습니다.

부탁드립니다...ㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <ctime>

using namespace std;

/** 예 => 답: 5150
10 10 1000
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
6 6 1
7 7 1
8 8 1
9 9 1
10 10 1
*/

int N, M, K;
int pos[8][2] = {{-1, -1},{-1, 0},{-1, 1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; // 8방위
int map[15][15], feed[15][15], deadTreeFeed[15][15];
deque<vector<int>> tree;    // 전체 나무 리스트
vector<int> tree5;  // 5배수가 되는 나무의 tree deque의 index값

void fall() {

    int treeTotalCnt = tree5.size();

    int addCnt = 0;
    for (int i = 0; i < treeTotalCnt; i++) {

        // 8방위에 나무 추가
        for (int idx = 0; idx < 8; idx++) {

            int nextX = tree[tree5[i] + addCnt][0] + pos[idx][0], nextY = tree[tree5[i] + addCnt][1] + pos[idx][1];

            // 땅의 범위를 초과하지 않는 경우 => 나무 번식.
            if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                tree.push_front({nextX, nextY, 1});
                addCnt++;
            }
        }

    }

    tree5.clear();    // 5배수의 나무 index 리스트는 비워준다

}

void spring() {

    int idx=0;
    int treeTotalCnt = tree.size();

    while (treeTotalCnt > 0) {
        treeTotalCnt--;

        int x = tree.front()[0], y = tree.front()[1], age = tree.front()[2];
        tree.pop_front();    // 나무 정보는 pop해준다

        // 아직 양분이 있는 경우
        if (map[x][y] >= age) {
            map[x][y] -= age;
            age += 1;

            // 나이가 5배수인경우 vector에 넣는다.
            if (age % 5 == 0) {
                tree5.push_back(idx);
            }

            tree.push_back({x, y, age});    // 정보를 다시 맨뒤에 넣어준다.
            idx++;
        }
        else { // 양분이 없어서 나무가 죽는 경우
            deadTreeFeed[x][y] += (age/2);  // 나무나이를 2로 나눈 값이, 나무가 있던 칸에 양분으로 추가
        }
    }

}


void winter() {

    // 땅에 양분을 추가
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // 입력받은 양분값과 여름에 더해져야할 양분값을 map에 저장한다
            map[i][j] += (feed[i][j] + deadTreeFeed[i][j]);
            deadTreeFeed[i][j] = 0; // 죽은 나무 양분값은 초기화시켜준다
        }
    }

}

void sortByAge() {
    // 나이 기준으로 오름차순 정렬해준다.
    sort(tree.begin(), tree.end(),
         [](const vector<int> &a, const vector<int> &b) {
             return a[2] < b[2];
         });
}

int main() {

    int answer = 0;

    scanf("%d %d %d", &N, &M, &K);
    // A배열 저장
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> feed[i][j];  // 겨울에 주는 양분 값
            map[i][j] = 5;  // 기본양분 : 5 설정
        }
    }
    // 나무정보 저장
    for (int i = 0; i < M; i++) {

        int x, y, age;
        scanf("%d %d %d", &x, &y, &age);

        tree.push_back({x - 1, y-1, age}); // 0: x위치, 1: y위치, 2: 나이

    }

    // 나무list를 AGE 오름차순으로 정렬한다.
    sortByAge();

    // K년이 될때까지 아래를 반복한다.
    for (int year = 0; year < K; year++) {
        // 봄(season = 1): 앙분 - 나무나이 and 나무나이 +1, 만약 2개이상이면 어린나무부터 양분을 먹는다. if(양분 == 0) 나무 죽음
        spring();
        // 여름(season = 2): 양분 += 죽은나무나이/2 ==> 봄에서 배열에 양분값을 저장해주고, 겨울에 값을 더해준다.
//        summer();
        // 가을(season = 3): 나무나이%5 == 0 인경우, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
        fall();
        // 겨울(season = 4): map[x][y] += 양분[x][y]
        winter();
    }

    // 살아있는 나무의 수를 구한다.
    answer = tree.size();
    cout << answer << endl;

    return 0;
}

pl0892029 3년 전 1

0ms 으로 풀지는 못했지만, 일단(?) 풀려서 답변 드립니다.

동적 계획법으로 접근해봅시다. 같은 구역에 있는, 같은 나이의 나무들은 따로 분리해서 생각할 이유가 없습니다.

따라서

tree[x][y][age] = (x,y)좌표에 있는 age의 나이를 가진 나무의 수

로 일괄적으로 처리할 수 있습니다.

K <= 1000 이고, 1 <= x, y <= N 이며 age는 최악의 나이를 계산하면 됩니다.

시간복잡도는 O(K * N^2 * age) 로 푸실 수 있습니다.

bongbbi 3년 전 0

말씀해주신대로, 3차원배열로 x,y 좌표에 나이별 나무 개수를 따로 저장하니 해결이 되었네요! 감사합니다

단순히 모든나무에 대해서 list로 저장해 구현했었는데, 시간차이가 많이나는가봅니다..ㅠㅠ

jjack1234 3년 전 0

저는 내림차순으로 한번만 sort시켜서 vector를 stack처럼 사용하니 sorting에 시간을 많이 안써도 되서 시간초과를 없앨 수 있었습니다.

vector > tree(101, vector(0));

//simulation

for (int i = 0; i < k; i++) {
//spring & summer
for (int j = 0; j < n*n; j++) {
int r = j / n;
int c = j % n;
if (tree[j].empty()) { continue; }

int erase_idx = - 1;
for (int k = tree[j].size() - 1; k >= 0; k--) {
if (current[r][c] < tree[j][k]) { //양분 없으니 erase_idx부터의 나무는 다 죽게됨.
erase_idx = k;
break;
}
current[r][c] -= tree[j][k]; //자기 나이만큼 양분 감소
tree[j][k]++; //나이 한살 더먹음.
}
//summer
for (int k = erase_idx; k >= 0; k--) {
current[r][c] += tree[j][k] / 2;
tree[j].erase(tree[j].begin() + k);
}
}

//autumn
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
int idx = j * n + k;
if (tree[idx].empty()) { continue; }
for (int itr = 0; itr < tree[idx].size(); itr++) {
if (tree[idx][itr] % 5 == 0) {
bool row_1 = (j-1 >= 0);
bool row_2 = (j+1 < n);
bool col_1 = (k-1 >= 0);
bool col_2 = (k+1 < n);
if(row_1) {
if (col_1) {
tree[idx - n - 1].push_back(1);
}
tree[idx - n].push_back(1);
if (col_2) {
tree[idx - n + 1].push_back(1);
}
}
if (col_1) {
tree[idx - 1].push_back(1);
}
if (col_2) {
tree[idx + 1].push_back(1);
}
if (row_2) {
if (col_1) {
tree[idx + n -1].push_back(1);
}
tree[idx + n].push_back(1);
if (col_2) {
tree[idx + n + 1].push_back(1);
}
}
}
}
}
}

//winter
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
current[j][k] += add[j][k];
}
}

}

3차원 배열도 좋은 방법 같은데, age만큼 메모리를 엄청 잡아놓고 써야 되는 것 아닌가요??

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

공손히 부탁드립니다.. 2주째 시간초과 제발 도와주세요

bongbbi 3년 전 0

pl0892029 3년 전 1

bongbbi 3년 전 0

jjack1234 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말