[백준 19951번] 태상이의 훈련소 생활 (Java)

끝없는 dp 생활!

 

이번 문제는 누적합+dp문제다.

맨날 똑같은 문제만 풀고

새로운 문제는 나몰라라해서

다양한 문제를 풀어보고자 골랐다.

 

---

문제

 

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

 

 

 

 

---

풀이

 

알고리즘 설계 [접근 방법] : 누적합+DP

모든 지시를 처음부터 끝까지 계산하면 시간 초과가 발생한다. 그러므로, 처음과 끝만 저장한 후 누적합으로 풀면 O(n)의 속도로 풀 수 있다.

처음부터 끝까지 계산해야 하는 k값을 입력받는다. 그리고 처음 시작하는 인덱스 a에 k값을 저장한 후 끝나는 지점, 즉 b+1지점에 -k값을 저장한다.

왜냐하면, a부터 끝까지 +k값을 계산한다고 가정하면, b+1지점부터 끝까지는 +k값을 계산하면 안된다. 그러므로 b+1지점부터는 -k값을 해주어야 하기 때문이다. 

 

1) 문제의 예시를 보면 1 5 -3을 보면 1번부터 5번까지 -3을 계산해야 한다. 그럼 인덱스 1번 배열에 -3을 저장하고, 끝난 후인 인덱스 6에 3을 저장한다

2) 두번째 지시인 6 10 5도 마찬가지로 인덱스 6번에 5를 저장하고, 인덱스 11에 -5를 저장한다.

3) 세 번째 지시인 2 7 2도 마찬가지로 인덱스 2번에 2를 저장하고, 인덱스 8에 -2를 저장한다.

 

표에 인덱스 1번부터 10번까지 나타났다고 해보자

-3

2

8

-2

 

그럼 이제, 누적합을 할 차례다. 반복문을 돌면서 현재 값은 현재 값+전의 값이 된다.

첫 번째 인덱스는 -3을 계산해주면 되는 것이고, 두 번째 인덱스의 값은 -3+2이므로 -1값을 해주면 된다. 

누적합이 반복된 표는 아래와 같다.

-3

-1

-1

-1

-1

7

7

5

5

5

 

이 값을 처음 받은 배열의 값과 더하면 된다.

 

풀이 과정

1.

배열 길이 n과 지시 사항 개수 m을 입력받는다.

 

2.

배열이 1부터 시작이므로, 배열 arr의 크기를 n+1로 설정한다. 그리고 값을 입력받는다.

 

3.

배열이 1부터 n+1까지 필요하므로, 누적합 배열 dp를 n+2 크기만큼 설정한다.

지시 사항 개수 m만큼 지시 사항을 입력받는다.

시작 인덱스인 start, 끝 인덱스인 end, 그리고 계산해야 하는 값 k를 입력받은 후, dp[start]+=k를 dp[end+1]-=k를 계산한다,

 

4.

처음부터 끝까지 dp배열을 돌면서, dp[현재] = dp[현재]+dp[현재-1]값을 진행한다.

그리고 처음 입력받은 배열 arr과 더한 값을 StringBuilder에 저장한다.

 

5.

StringBuilder를 출력한다.

 

---

코드

 

import java.util.*;

public class Test_19951_태상이의훈련소생활 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] arr = new int[n+1];
		for(int i=1; i<arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		
		//수행 : 누적합
		int[] dp = new int[n+2];
		for(int t=0; t<m; t++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			int k = sc.nextInt();
			
			dp[start] = dp[start]+k;
			dp[end+1] = dp[end+1]-k;
		}
		
		//출력
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<arr.length; i++) {
			dp[i] = dp[i]+dp[i-1];
			sb.append((arr[i]+dp[i])+ " ");
		}
		
		System.out.println(sb.toString());
		
	}
}