[백준] 단계별로 풀어보기(단계:16, 누적합,JAVA)2559번, 수열

문제 링크

2559번: 수열

---

주의사항

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

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

---

문제 설명

---

접근 방법

누적합이란?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

 

이 문제에 핵심은

1. N개의 온도에서 K일 동안의 연속된 온도 합의 최대값을 구해야 합니다.

 

저는 이 문제를 누적합을 이용하여 간단하게 해결하였습니다.

 

사용한 배열

 

DP : 누적합 저장 배열

 

num : 입력되는 숫자 저장 배열

예제입력 1의 입력된 숫자들을 누적합에 대한 표로 나타내면

	3	-2	-4	-9	0	3	7	13	8	-3
누적합	3	1	-3	-12	-12	-9	-2	11	19	16

예제입력에서 K = 2

문제에 그림을 분석해보면 누적합으로 규칙을 만들 수 있습니다.

 

연속된 온도 합 = DP[i+K] - DP[i]

 

DP[0]은 온도가 저장되어 있지 않기 때문에 0으로 초기화하였습니다.

첫 번째 값 3에서 2일 연속 온도의 합은

DP[0+2] - DP[0] = DP[2] - DP[0] = -3 + 0 = -3

 

네 번째 값 -9에서 2일 연속 온도의 합은

DP[3+2] - DP[3] = -12 - (-3) = -9

 

예제입력 2에서도 동일하게 적용 가능하다.

온도의 내용은 같기 때문에 예제입력1에 누적합을 그대로 이용하겠습니다.

 

두 번째 값 -2에서 5일 연속 온도의 합은

DP[1+5] - DP[1] = DP[6] - DP[1] = -9 - 3 = -12

 

위와 같이 나오는 온도의 합에서 가장 큰 수를 결과로 출력하면 됩니다.

 

예제입력1에서는 가장 큰 합인 21이 출력되었으며

예제입력2에서는 가장 큰 합인 31이 출력되었습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N, K와 N개의 온도를 받습니다.

2. N개의 숫자를 num에 저장할 때 누적합 DP도 같이 구합니다.

3. 규칙을 통해 합의 최대값을 구하여 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 N과 K, N개의 온도를 분리하였습니다.
• N개의 온도를 저장할 때 DP도 같이 구하였습니다
• K일 연속되는 온도의 합의 최대값을 구하는 cal 함수를 만들었습니다.
• BufferedWriter에 최대값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 규칙과 DP함수를 이용하여 K일 연속되는 온도의 합의 최대값을 구하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N,K;
	static int[] num, DP;	//온도 저장 배열, 누적합 저장 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
       	//------입력값 저장 및 배열 초기화
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		num = new int[N+1];
		DP = new int[N+1];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=1;i<=N;i++) {
			num[i] = Integer.parseInt(st.nextToken());	//온도 저장
			DP[i] = DP[i-1] + num[i];		//누적합 저장
		}
		int result = cal();		//함수 실행 및 최대값 저장
		bw.write(result + "\n");		//최대값 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    //K일 연속 온도의 합의 최대값을 구하는 함수
	static int cal() {
		int max = Integer.MIN_VALUE;		//최대값 초기화
		for(int i=0;i<=N-K;i++) {
			int temp = DP[i+K] - DP[i];		//규칙
			max = Math.max(max, temp);		//최대값 비교하기
		}
		return max;		//최대값 반환
	}
}