[백준, Java] 25606번, 장마, (누적합)

문제 링크

25606번: 장마

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 매일 아크릴 상자에 내리는 비의 양을 모아서 실내에 저장합니다.

2. 실내에 저장한 물은 매일 M만큼 증발하며, 상자에 존재하는 물의 양이 M보다 작을 경우 모두 증발합니다.

3. 다빈이가 측정을 완료했을 때 교수님은 Q개의 질문을 진행합니다.

4. Q개의 질문에 대한 답을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 누적합을 통해서 질문에 대한 모든 답을 탐색합니다.

 

3. 탐색이 끝난 뒤 Q개의 질문에 대한 답을 결과로 출력합니다.

 

누적합(물의 양, 증발된 양)

 

물의 양과 증발된 양에 대해서 누적합을 진행할 것입니다.

 

물의 양

 

물의 양은 단순히, 지금까지 아크릴 상자에 담긴 모든 물의 양에 대해서 누적합을 진행합니다.

 

예를 들면,

 

물의 양	2	4	6	8
누적합	2	6	12	20

 

점화식 : sum[i] = sum[i-1] + cur(현재 물의 양)

 

증발된 양

 

증발된 양을 구하는 것이 이 문제에 핵심입니다.

 

각 날의 비의 양이 언제까지 증발되는지 알 수 있습니다.

 

만약, 매일 증발되는 양 : 5

 

어느 날 내린 비의 양이 12이면

 

(12 ÷ 5) + 1 =  3일까지는 물이 증발됩니다.

 

▶ 2일 동안은 M만큼 증발하고 남은 1일은 12 % 5 = 2만큼 증발한다는 사실을 알 수 있습니다.

 

이것을 이용하면, 날마다 증발되는 누적합을 구할 수 있습니다.

 

 

물의 양

2

4

6

8

 

매일 증발하는 물의 양 : 3

 

2일 때 : (2 ÷ 3) + 1 = 1일

 

2 % 3 = 2 : 마지막 날 증발하는 물의 양

 

물의 양	2	4	6	8
증발한 물의 양	0	2

 

1일동안 증발하는 것이 마지막 증발이기 때문에 2만큼 증발하는 것입니다.

 

4일 때 : (4 ÷ 3) + 1 = 2일

 

4 % 3 = 1 : 마지막 날 증발하는 물의 양

 

물의 양	2	4	6	8
증발한 물의 양	0	2	5

2일에서 1일은 M만큼 증발, 마지막 날은 1만큼 증발하여 위에 표에서는 3만큼 증발한 값을 더한 것을 확인할 수 있습니다.

 

위와 같이 모두 진행한다면

 

물의 양	2	4	6	8
증발한 물의 양	0	2	5	9

 

 

이제 교수님의 질문에 대답을 진행하겠습니다.

 

1.  1 t : 장마 시작 t일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가?

 

▶ t일 물의 누적합 - t일 증발된 양의 누적합

 

2. 2 t : 장마 시작 t일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가?

 

▶ t일 물의 누적합 - (t-1)일 증발된 양의 누적합

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 5

 

M : 10

 

Q : 5

 

물의 양

10

20

5

8

11

 

 

2. 누적합을 통해서 질문에 대한 모든 답을 탐색합니다.

 

1) 물의 누적합 구하기

 

 

물의 양	10	20	5	8	11
누적합	10	30	35	43	54

 

 

 

2) 증발된 물의 양 구하기

 

 

물의 양

10

20

5

8

11

10일 때 : (10 ÷ 10) + 1 = 2일

 

10 % 10 = 0 : 마지막 날 증발하는 물의 양

 

 

물의 양	10	20	5	8	11
누적합	0

 

20일 때 : (20 ÷ 10) + 1 = 3일

 

20 % 10 = 0 : 마지막 날 증발하는 물의 양

 

물의 양	10	20	5	8	11
누적합	0	10

 

5일 때 : (5 ÷ 10) + 1 = 1일

 

5 % 10 = 5 : 마지막 날 증발하는 물의 양

 

물의 양	10	20	5	8	11
누적합	0	10	20

8일 때 : (8 ÷ 10) + 1 = 1일

 

8 % 10 = 8 : 마지막 날 증발하는 물의 양

 

물의 양	10	20	5	8	11
누적합	0	10	20	35

11일 때 : (11 ÷ 10) + 1 = 2일

 

11 % 10 = 1: 마지막 날 증발하는 물의 양

 

물의 양	10	20	5	8	11
누적합	0	10	20	35	43

 

누적합을 한 번에 표현하면

 

물의 양	10	20	5	8	11
물 누적합	10	30	35	43	54
증발양 누적합	0	10	20	35	43

 

 

3. 탐색이 끝난 뒤 Q개의 질문에 대한 답을 결과로 출력합니다.

 

1 1(t) : 10 - 0  = 10

 

1 3(t) : 35 - 20 = 15

 

1 5(t) : 54 - 43 = 11

 

2 2(t) : 10 - 0 = 10

 

2 4(t) : 35 - 20 = 15

 

10

15

11

10

15

을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 물의 정보들을 띄어쓰기 기준으로 나누었습니다.
• 물의 양과 증발되는 양에 따라 누적합을 진행합니다.
• 누적합이 끝났을 때 Q개의 질문에 대한 결과를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        //누적합 저장 배열
        int[][] sum = new int[N+1][2];
        //증발되는 물에 관해서 끝나는 날을 저장하는 배열
        int[][] checking = new int[N+1][2];
        st = new StringTokenizer(br.readLine()," ");
        int idx = 0;	//현재 M만큼 증발되는 박스 개수
        //누적합 진행
        for(int i=1;i<=N;i++){
            int num = Integer.parseInt(st.nextToken());
            //물의 양 누적합 진행
            sum[i][0] = sum[i-1][0] + num;
            sum[i][1] = sum[i-1][1];
            //증발되는 양이 이번이 마지막 날인 경우가 존재할 때
            if(checking[i][0] > 0){
                idx -= checking[i][0];
                //마지막 증발되는 양 누적합에 더하기
                sum[i][1] += checking[i][1];
            }
            //M만큼 증발 진행
            sum[i][1] += idx * M;
            //현재 물의 양에 따라 증발되는 구간 설정
            int nxt = i + (num / M) + 1;
            if(nxt <= N){	//N일 안에 증발되는 구간이 없어질 때
                checking[nxt][0]++;
                checking[nxt][1] += num % M;
            }
            idx++;
        }
        //질문에 대한 대답 진행하기
        for(int i=0;i<Q;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int command = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            //1번 질문 진행
            if(command == 1){
                bw.write(String.valueOf(sum[t][0] - sum[t][1]));
            }else{		//2번 질문 진행
                bw.write(String.valueOf(sum[t][1] - sum[t-1][1]));
            }
            bw.newLine();
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
}