글 읽기 - dp??로 풀었는데 이렇게 푸는게 맞는건지 잘 모르겟네요;;

bsdlcksdn 8년 전 0

부분합을 구하길래 dp가 생각나서 우선 입력받을때 값을 입력받은 것 까지의 합을 dp배열에 저장합니다.

그리고 a==1이면 visit이라는 배열을 만들어서 visit[][0]에는 위치(idnex)를 , visit[][1]에는 바꿀 값(c)를 저장합니다.

a==2이면 sum이라는 변수에 2~5구간이라고 치면 dp[5]-dp[1]을 하여 구간합을 구하고

visit배열을 탐색하면서 2~5구간 사이에 있는 index(=visit[][0])을 확인하여 있으면 기존의 배열의 값 arr[visit[][0]]을 빼고 / visit[][1]을 더하

는 방식으로 만들었습니다.

testcase도 바꿔가면서 돌려보는데 채점(2%)에서 계쏙 틀리네요;;; 뭐가 문제일까요?

시간도 m,k가 10000씩이니까 최대 20000이고 / visit배열에서 찾아도 10000이면 약 2억정도 돌것같은데;; 시간상에도 문제가있을까요?

#include <iostream>
using namespace std;

int n, m, k;
long long int arr[1000010];
long long int dp[1000010];
long long int visit[1000010][2];
long long int sum;

int a, b, c;

int main() {

	//입력
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		dp[i] = dp[i - 1] + arr[i];
	}

	int count = m + k;
	int index = 0;

	while (count--) {
		//초기화
		sum = 0;
		//

		cin >> a >> b >> c;

		//값 저장
		if (a == 1) {
			visit[index][0] = b;
			visit[index][1] = c;
			index++;
		}
		//합구하기
		else {
			int cnt = index-1;
			sum = dp[c] - dp[b-1];

			while (cnt>=0) {

				if (visit[cnt][0] >= b && visit[cnt][0] <= c) {
					//cout <<"sum : "<<sum<< " visit : " << visit[cnt][0] << " / " << visit[cnt][1] << endl;

					//음수면 더하고
					if (arr[visit[cnt][0]] < 0) {
						sum += arr[visit[cnt][0]];
					}
					//양수면 빼고
					else {
						sum -= arr[visit[cnt][0]];
					}

					sum += visit[cnt][1];
				}
				cnt--;
			}
			
			cout << sum << endl;
		}
	}

}