글 읽기 - 14943. 벼룩시장 문제 질문있습니다.(시간초과)

minjae200 5년 전 0

Greedy Algorithm을 적용하여

array value가 음수이면 for(dist) 에서 거리를 늘려가며 0을 만들어주는 형식으로 구현하였습니다.

N이 100000이라 당연히 시간초과가 뜰건 예상을 햇지만 해결방법이 떠오르질 않습니다. 충고나 조언주실 고수분 없으신가요

해결하고싶습니다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
long long ans;
int *store;

void solve(void)
{
	for (int i = 0; i < N; i++) {
		if (store[i] < 0) {
			for (int dist = 1; dist < N; dist++) {
				if (i - dist >= 0 && store[i-dist] > 0) {
					if (abs(store[i]) > store[i - dist]) {
						store[i] += store[i - dist];
						ans += dist * store[i - dist];
						store[i - dist] = 0;
					}
					else {
						store[i - dist] += store[i];
						ans += dist * abs(store[i]);
						store[i] = 0;
					}
				}
				if (i + dist < N && store[i+dist] > 0) {
					if (abs(store[i]) > store[i + dist]) {
						store[i] += store[i + dist];
						ans += dist * store[i + dist];
						store[i + dist] = 0;
					}
					else {
						store[i + dist] += store[i];
						ans += dist * abs(store[i]);
						store[i] = 0;
					}
				}
			}
		}
	}
}

int main(void)
{
	cin >> N;
	store = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> store[i];
	}

	solve();
	cout << ans << endl;
	return 0;
}

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

문제

문제

출처

ICPC

14943. 벼룩시장 문제 질문있습니다.(시간초과)

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말