[백준, Java] 15912번, 우주선 만들기, (DP)

문제 링크

15912번: 우주선 만들기

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 모든 부품에는 W(무게), E(에너지)가 존재합니다.

2. 각 부품을 구매할 때는 W × E 비용을 지불합니다.

3. 연속된 부품을 구매할 때는 maxW × maxE 비용을 지불합니다.

4. X, Y(X < Y)일 때 X부품이 구매되지 않으면 Y부품은 구매하지 못합니다.

5. 모든 부품을 구매하는 최소 비용을 결과로 출력합니다.

 

★ 4번 핵심을 간단히 표현하면 각 부품은 1번부터 순서대로 구매해야 한다!

 

알고리즘 진행 순서.

 

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

 

2. DP을 이용해서 모든 부품을 구매하였을 때 최소 비용을 탐색합니다.

 

3. 탐색을 통해 얻은 최소 비용을 결과로 출력합니다.

 

 

DP(각 부품까지 구매하는 최소 비용)

 

DP[] 에 대한 메모이제이션을 진행합니다.

 

DP[i] : 1 ~ i번째까지 부품을 구매할 때 최소 비용

 

i번째 부품을 구매할 때 선택할 수 있는 방법은

 

1개, 2개, 3개 ... i-1개, i개 연속 구매하는 방법이 존재합니다.

 

예를 들어, i가 4이면

 

(1, 2, 3) (4) 구매

 

(1, 2) (3, 4) 구매

 

(1), (2, 3, 4) 구매

 

() (1, 2, 3, 4) 구매

 

여기서 우리는 순차적으로 DP[]을 채워나아갔다면 (1, 2, 3) (4)일 때에는 DP[3]의 값을 사용하면 중복된 탐색을 방지할 수 있습니다.

 

식으로 표현하면

 

(1, 2, 3) (4) : DP[3] + 4번 부품 구매 비용

 

(1, 2) (3, 4) : DP[2] + 3 ~ 4번 연속된 부품 구매 비용

 

...

 

위처럼 DP[]을 이용해서 중복된 탐색을 방지하고 최소 비용의 값들을 구할 수 있습니다.

 

※ 1개의 부품 구매 = 1개의 연속된 부품 구매

 

위 과정을 모두 끝나면 DP[N]의 값은 1 ~ N 모든 부품을 구매하였을 때 최소 비용이 됩니다.

 

 

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

 

예제입력 1.

 

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

 

N : 5

 

부품	1	2	3	4	5
무게(W)	1	2	3	4	5
에너지(E)	3	2	8	9	4

 

 

2. DP을 이용해서 모든 부품을 구매하였을 때 최소 비용을 탐색합니다.

 

DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0

 

 

1번 부품 관련 탐색 진행

 

() (1) : DP[0] + maxW(1) × maxE(3) = 3

 

DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3

 

2번 부품 관련 탐색 진행

 

(1) (2) : DP[1] + maxW(2) × maxE(2) = 7

 

() (1, 2) : DP[0] + maxW(2) × maxE(3) = 6

 

DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3	6

 

3번 부품 관련 탐색 진행

 

(1, 2) (3) : DP[2] + maxW(3) × maxE(8) = 30

 

(1) (2, 3) : DP[1] + maxW(3) × maxE(8) = 27

 

() (1, 2, 3) : DP[0] + maxW(3) × maxE(8) = 24

 

 

DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3	6	24

 

4번 부품 관련 탐색 진행

 

(1, 2, 3) (4) : DP[3] + maxW(4) × maxE(9) = 60

 

(1, 2) (3, 4) : DP[2] + maxW(4) × maxE(9) = 42

 

(1) (2, 3, 4) : DP[1] + maxW(4) × maxE(9) = 39

 

() (1, 2, 3, 4) : DP[0] + maxW(4) × maxE(9) = 36

 

DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3	6	24	36

 

 

5번 부품 관련 탐색 진행

 

(1, 2, 3, 4) (5) : DP[4] + maxW(5) × maxE(4) = 81

 

(1, 2, 3) (4, 5) : DP[3] + maxW(5) × maxE(9) = 69

 

(1, 2) (3, 4, 5) : DP[2] + maxW(5) × maxE(9) = 51

 

(1) (2, 3, 4, 5) : DP[1] + maxW(5) × maxE(9) = 48

 

() (1, 2, 3, 4, 5) : DP[0] + maxW(5) × maxE(9) = 45

 

탐색 결과 DP 테이블

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3	6	24	36	45

 

 

 

 

3. 탐색을 통해 얻은 최소 비용을 결과로 출력합니다.

 

i	0	1	2	3	4	5
1 ~ i 최소 비용	0	3	6	24	36	45

 

DP[N] : 1 ~ N 부품을 구매할 때 최소 비용

 

▶ DP[5] = 45

 

 

45을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 부품의 정보를 띄어쓰기 기준 나누었습니다.
• DP[]을 통해서 불필요한 반복 연산을 방지하고 1부터 각 부품까지 최소 비용을 탐색합니다.
• 탐색을 통해 얻은 DP[N] 1 ~ 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()," ");
        long[] W = new long[N+1];
        long[] E = new long[N+1];
        //입력값 저장
        for(int i=1;i<=N;i++){
            W[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i=1;i<=N;i++){
            E[i] = Long.parseLong(st.nextToken());
        }
        long[] DP = new long[N+1];
        //DP을 통해 각 부품까지 구매하는 최소 비용 구하기
        for(int i=1;i<=N;i++){
            DP[i] = W[i] * E[i] + DP[i-1];
            long maxW = W[i];
            long maxE = E[i];
            //감소시키면서 연속되는 범위 늘리기
            for(int j=i-1;j>0;j--){
                maxW = Math.max(maxW, W[j]);
                maxE = Math.max(maxE, E[j]);
                DP[i] = Math.min(DP[i], maxW * maxE + DP[j-1]);
            }
        }
        //DP[N] : 1 ~ N 부품 꾸매 최소 비용BufferedWriter 저장
        bw.write(String.valueOf(DP[N]));
        bw.flush();  //결과 출력
        bw.close();
        br.close();
    }
}