BOJ 19951 태상이의 훈련소 생활

https://www.acmicpc.net/problem/19951

19951번: 태상이의 훈련소 생활

 

2부터 5 까지 2만큼 파고  1부터 3까지 9만큼 파라는 명령이면 

prefix[2] =2 , prefix[5+1]=-2

prefix[1] =9 , prefix[3+1]=-9   (올라가기 시작하는 곳에 더할값을 더하고 더하는 값이 끝나는 다음 곳 부터는 다시 그 값을 뺴서 리셋 해주면 된다.)

로 기록하고 

prefix 배열을 돌면서

prefix[i] = prefix[i-1]+prefix[i]

로 prefix값을 구하면 된다.

 

그후 다시 원본 배열에서 계산해주면 된다.

 

 

import java.util.*;
import java.io.*;
public class Main
{   
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    String[] input1 = br.readLine().split(" ");
	    int n = Integer.valueOf(input1[0]);
	    int m = Integer.valueOf(input1[1]);
	    int[] ground = new int[n];
	    int[] prefix = new int[n+2];
	    
	    String[] input2 = br.readLine().split(" ");
	    
	    for(int i=0;i<n;i++){
	        ground[i] = Integer.valueOf(input2[i]);
	    }
	    
	    for(int i=0;i<m;i++){
	        String[] input3 = br.readLine().split(" ");
	        int a = Integer.valueOf(input3[0]);
	        int b = Integer.valueOf(input3[1]);
	        int c = Integer.valueOf(input3[2]);
	        prefix[a]+=c;
	        prefix[b+1]-=c;
	    }
		for(int i=1;i<n+1;i++){
		    prefix[i]=prefix[i-1]+prefix[i];
		    ground[i-1] =ground[i-1]+prefix[i]; 
		    bw.write(ground[i-1]+" ");
		}
	    
		
		bw.flush();
	}
}