[알고리즘] 백준 19951 누적합 문제풀이

태상이의 훈련소 생활 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

2980

1759

1382

59.620%

문제

2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.

연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 b번 칸까지 높이 k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.

태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.

불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.

입력

첫 줄에 연병장의 크기 N과 조교의 수 M이 주어진다.

둘째 줄에 연병장 각 칸의 높이 Hi가 순서대로 N개 주어진다.

셋째 줄부터 M개의 줄에 각 조교의 지시가 주어진다.

각 조교의 지시는 세 개의 정수 a, b, k로 이루어져 있다.

• k ≥ 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 늘어나도록 흙을 덮어야 한다.
• k < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 줄어들도록 흙을 파내야 한다.

출력

모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• -10,000 ≤ Hi ≤ 10,000
• N, M, Hi는 정수
• 조교의 지시
  • 1 ≤ a ≤ b ≤ N
  • |k| ≤ 100

예제 입력 1 복사

10 3
1 2 3 4 5 -1 -2 -3 -4 -5
1 5 -3
6 10 5
2 7 2

 

예제 출력 1 복사

-2 1 2 3 4 6 5 2 1 0

 

 

• 초기 연병장의 상태: 1 2 3 4 5 -1 -2 -3 -4 -5
• 첫번째 지시 (1 5 -3)를 수행 한 뒤: -2 -1 0 1 2 -1 -2 -3 -4 -5
• 두번째 지시 (6 10 5)를 수행한 뒤: -2 -1 0 1 2 4 3 2 1 0
• 세번째 지시 (2 7 2)를 수행한 뒤: -2 1 2 3 4 6 5 2 1 0

출처

University > 인하대학교 > 2020 IGRUS Newbie Programming Contest H번

• 문제를 검수한 사람: baekjoon, chobe1, gunwookim, panda959595, rhs0266, saemy90, tyoungs, zxcvber
• 문제를 만든 사람: gsts007

 

알고리즘 분류

• 누적 합

문제풀이 

이번 문제는 누적합을 이용해서 푸는 문제인데 조교가 지시하는 높이의 변화를 delta라는 배열에 각각의 조교가 지시하는 변화량을 기록하고, accdelta배열에 전체 변화량을 기록한 다음,, 원래의 높이가 기록된 배열에 accdelta배열에 기록된 값을 적용하여 전체의 높이 변화를 한번에 계산을 한다. 

import java.util.*;
import java.io.*;

public class Solution{
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N;
	static int M;
	
	
	
	public static void main(String[] args) throws IOException{
		//첫번재 라인 N과 M을 한줄로 입력 받음
		st = new StringTokenizer(br.readLine());
		
		//N을 입력
		N = Integer.parseInt(st.nextToken());
		
		//M을 입력 
		M = Integer.parseInt(st.nextToken());
		//운동장의 높이를 입력 받기
		int[]  ground = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for(int i =1; i <=N; i++) {
			
			ground[i] = Integer.parseInt(st.nextToken());
			
		}
		
		//변화량을 기록할 delta 배열 생성 0번과 마지막 N을 위해 +2를 더함
		int[] delta = new int[N+2];
		//조교위 수 만큼 지시를 수행
		while(M-- >0) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			delta[start] += height;
			delta[end+1] -= height;
		}
		int[] accdelta = new int[N+1];
		for( int i =1; i <=N; i++) {
			accdelta[i] = accdelta[i-1] +delta[i];
		}
		
		for(int i =1; i<=N; i++) {
			bw.write(ground[i] + accdelta[i]+" ");
		}
		bw.flush();
	}
}