[백준, Java] 2616번, 소형기관차(DP, 누적합)

문제 링크

2616번: 소형기관차

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 소형 기관차는 3대가 항상 존재하며 최대로 끌 수 있는 객차도 동일합니다.

2. 객차를 끌고 갈 때에는 연속적으로 연결되어 있어야합니다.

3. 소형 기관차 3대가 최대로 운송할 수 있는 손님의 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 점화식을 통해 소형 기관차 3대가 가질 수 있는 최대 손님의 수를 계산합니다.

 

3. 최대 손님의 수를 결과로 출력합니다.

 

 

점화식

 

 

DP[i][j] = Math.max(DP[i][j-1], DP[i-1][j-M] + (sum[j] - sun[j-M]))

 

i : i번째 소형기관차

j : j개의 객차를 선택할 때

sum : 객차 고객의 수 누적합

 

※ j는 i *M부터 시작합니다.

→ 최대의 손님을 태우려면 소형 기관차는 최대의 객차를 끌고 가야하기 때문에 최소 i * M개는 끌고 갑니다.

 

예.

M = 2일 때

DP[2][6] = 2번째 소형기관차가 5~6번째 객차를 가져갈 때

 

DP[2][6] = Math.max(DP[2][5], DP[1][4] + (sum[6] - sum[4]))

 

 

예제입력 1.

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

N : 7

M : 2

 

35

40

50

10

30

45

60

누적합

35

75

125

135

165

210

270

 

2. 점화식을 통해 소형 기관차 3대가 가질 수 있는 최대 손님의 수를 계산합니다.

 

점화식을 기준 계산 진행!!

 

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	75	90	90	90	90	105
2	0	0	0	0	135	135	165	195
3	0	0	0	0	0	0	210	240

 

 

3. 최대 손님의 수를 결과로 출력합니다.

 

 

DP[3][7] : 240

 

240 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 객차의 정보를 저장합니다.
• 반복문으로 점화식 기준 계산을 진행합니다.
• 계산이 끝난 뒤 DP[3][N](최대 손님 수)을 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));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] sum = new int[N+1];	//누적합 배열
        int[][] DP = new int[4][N+1];	//점화식 관련 저장 배열
        //누적합 구하기
        for(int i=1;i<=N;i++)
            sum[i] += sum[i-1] + Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        //점화식을 통한 계산 진행
        for(int i=1;i<4;i++){
            for(int j=i * M;j<=N;j++)
                DP[i][j] = Math.max(DP[i][j-1], DP[i-1][j-M] + sum[j] - sum[j-M]);
        }
        bw.write(String.valueOf(DP[3][N]));	//DP[3][N]의 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();

    }
}