글 읽기 - 시간초과 문제 해결 방안

asdsa2134 3년 전 0

deque를 이용하여 문제를 풀었는데 시간초과가 납니다. 최대한 줄인다고 줄인 것 같은데 deque 2차원 배열을 만드는 것 말고 제 코드에서 최적화 시켜서 통과시킬 수 있는 방법이 있을까요?

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;


struct pos { int x; int y; int age; 
bool operator<(pos a) const  {
    return age < a.age;
    }
};


int n, m, t, h, k;
const int INF = 1e9;

const int dx[8] = { 1, 1,0,-1, -1, -1,0, 1 };
const int dy[8] = { 0,-1, -1, -1,0,1,1,1 };

deque<pos> q;
int arr[11][11];
int add[11][11];

void Input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> add[i][j];
            arr[i][j] = 5;
        }
    }
    for (int i = 0; i < m; i++) {
        int x, y, age;
        cin >> y >> x >> age;
        q.push_back({ x,y,age });
    }
}
void solve() {
    sort(q.begin(), q.end());
    while (k--) {
        //봄
        int size = q.size();
		vector<pos> grow; // 번식할 나무
		vector<pos> dead; // 죽은 나무
        for (auto iter = q.begin(); iter != q.end(); ) {
            auto& cur = (*iter);

            if (arr[cur.y][cur.x] < cur.age) {// 나이보다 양분이 적으면 죽음
				dead.push_back(*iter); // 죽은 나무 추가
				iter = q.erase(iter); // 나무 삭제
            }
            else {
                arr[cur.y][cur.x] -= cur.age; // 양분 감소
                cur.age++; // 나이 1 증가
				iter++;
				if(cur.age % 5 == 0) // 번식할 나무 추가
					grow.push_back({ cur.x, cur.y, cur.age });
            }
        }

		//여름
		for (auto iter = dead.begin(); iter != dead.end(); iter++) {
			auto cur = (*iter);
			arr[cur.y][cur.x] += (cur.age / 2); // 죽은나무의 나이 /2 만큼 양분 추가
		}


        //가을
        size = grow.size();
        for (int i = 0; i < size; i++) { // 번식
            for (int j = 0; j < 8; j++) {
                int nx = dx[j] + grow[i].x;
                int ny = dy[j] + grow[i].y;

                if (nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
                else {
                    q.push_front({ nx, ny, 1 });
                }
            }
        }
        
        //겨울
        for (int i = 1; i <= n; i++) // 양분 추가
            for (int j = 1; j <= n; j++) arr[i][j] += add[i][j];
    }
    cout << q.size();
}

int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    Input();
    solve();
    return 0;
}

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

문제

문제

출처

ICPC

시간초과 문제 해결 방안

asdsa2134 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말