글 읽기 - 시간 초과가 날 수밖에 없는 접근일까요..?!

situodys 2년 전 0

제출 시에 채점 준비중 -> 틀렸습니다가 나옵니다..

나무의 정보를 담을 tree배열을 칸마다 deque로 선언하는 방식으론 시간초과가 날 수 밖에 없는 것인지 궁금합니다..!!

문제의 예시는 잘나오나 k=1000인 케이스에서 답을 보기까지 3분~5분정도가 걸리고 답도 오답(5182)이 나오네요ㅠㅠ

접근 방식 자체가 시간초과가 날수 밖에 없는 걸까요??
시간초과의 원인이 무엇인지 살펴봐주시면 감사하겠습니다..!!!!

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <utility>
#include <cctype>
#include <ctime>
#include <functional>
#include <cstdlib>
#include <iomanip>
#include <tuple>
#include <set>
using namespace std;
//    ios::sync_with_stdio(0);
//    cin.tie(0);


vector<int> dx = {0,-1,1,0,-1,-1,1,1};
vector<int> dy = {-1,0,0,1,-1,1,-1,1};

int n, m, k;
int ypos, xpos, age;
vector<vector<deque<int>>> tree(11, vector<deque<int>>(11));
vector<vector<bool>> isTreeExist(11, vector<bool>(11));
vector<vector<int>> food(11, vector<int>(11));
vector<vector<int>> foodByRobot(11, vector<int>(11));

void Spring_Summer() {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (!isTreeExist[i][j]) continue;
            //sort(tree[i][j].begin(), tree[i][j].end());
            for (int l = 0;l < tree[i][j].size();l++) {
                if (food[i][j] >= tree[i][j][l]) {
                    food[i][j] -= tree[i][j][l];
                    tree[i][j][l]++;
                }
                else {
                    int sum = 0;
                    int len = tree[i][j].size();
                    for (int si = l;si<len;  si++)
                        sum += tree[i][j][si];
                    food[i][j] += sum / 2;
                    tree[i][j].erase(tree[i][j].begin() + l, tree[i][j].end());
                    if (l == 0) isTreeExist[i][j] = false;
                    break;
                }                    
            }
        }
    }
}

void fall() {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (!isTreeExist[i][j]) continue;
            for (int l = 0;l < tree[i][j].size();l++) {
                if (tree[i][j][l] % 5 ==0) {
                    for (int dir = 0;dir < dx.size();dir++) {
                        int ny = i + dy[dir];
                        int nx = j + dx[dir];
                        if (ny < 0 || ny >= n || nx < 0 || ny >= n) continue;
                        tree[ny][nx].push_front(1);
                        isTreeExist[ny][nx] = true;
                    }
                }
            }
        }
    }
}

void winter() {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            food[i][j] += foodByRobot[i][j];
        }
    }
}

int countTree() {
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (!isTreeExist[i][j]) continue;
            cnt+= tree[i][j].size();
        }
    }
    return cnt;
}



int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    
    int treeCnt = 0;

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> foodByRobot[i][j];
            food[i][j] = 5;
        }
    }

    for (int i = 0;i < m;i++) {
        cin >> ypos >> xpos >> age;
        tree[ypos-1][xpos-1].push_back(age);
        isTreeExist[ypos-1][xpos-1] = true;
        treeCnt++;
    }


    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (!isTreeExist[i][j]) continue;
            sort(tree[i][j].begin(), tree[i][j].end());
        }
    }

    while (k--) {
        if (!treeCnt)
            break;
        Spring_Summer();
        fall();
        winter();
        treeCnt = countTree();
    }

    cout << treeCnt;


}

april338 2년 전 1

덱이 시간이 많이 걸리는 걸로 알아요

situodys 2년 전 0

다음날 해결 했습니다

k=1000일 때 예제 답이 잘못된걸 해결하니 풀리네요.. 시간 초과이 문제는 없었던 것 같습니다.

죽은 나무의 나이가 양분으로 바뀔 때 죽은 나무들의 나이 합/2 가 아닌 죽은 나무의 나이 각각 /2 후에 합을 해야합니다..!
간단하게 계산해도 바로 차이가 보이네요

situodys 2년 전 0

추가로 매번 계산했던 treeCnt를 반복이 끝나고 답을 출력하기 전 한번만 하는 것으로 수정했습니다.

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

문제

문제

출처

ICPC

시간 초과가 날 수밖에 없는 접근일까요..?!

situodys 2년 전 0

april338 2년 전 1

situodys 2년 전 0

situodys 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말