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

시간단축

Line: 41 sysout ->  bw.write( ) or StringBuilder

 

혼자 진짜 끙끙 오래 앓은 문제임..ㅠㅠ

 

누적합이라는 개념은 이해했는데

이걸 연속으로 넣는 문제들

기믹을 이해를 못했음..

 

브루트포스로는 당연히 절대 안되고

선형으로  해결해야함

 

Line:33 이게  핵심임

 accumK[a] += k;

 accumK[b+1] -= k;

 

a부터 b까지 k만큼의 흙을 덮거나 파야한다는 의미임..

기울기라고 생각하니까 이해가 편했음

a에서 b까지는 k라는 기울기가 유지되어야 한다는 것임

물론 조교의 지시가 M개 들어오니까

임의의 값 x가 있을 때, accum[x] = k1+k2+k3+.. +km일 것임

그것을 accum이라는 변수를 사용하여

선형으로 작업하는 부분에서 계속 갱신해주면됨

 

참고 :  https://blog.naver.com/deuslovelt/222502603550

카카오 1차 코테 6번 2차원 누적합

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        int M = stoi(str[1]);
        
        int[] res = new int[N+1];
        int[] accumK = new int[N+2];
        
        str = br.readLine().split(" ");
        for(int i=1; i<=N; i++) {
            res[i] = stoi(str[i-1]);
        }
        
        for(int i=1; i<=M; i++) {
            str = br.readLine().split(" ");
            int a = stoi(str[0]);
            int b = stoi(str[1]);
            int k = stoi(str[2]);
            
            accumK[a] += k;
            accumK[b+1] -= k;
        }
        int accum = 0;
        
        for(int i=1; i<=N; i++) {
            accum += accumK[i];
            res[i] += accum;
            System.out.print(res[i]+" ");
        }
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}