BOJ_15912_우주선 만들기 (Java, C++)

[Gold III] 우주선 만들기 - 15912

문제 링크

성능 요약

메모리: 2156 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 25일 22:59:23

문제 설명

<스타로드와 토끼는 토르를 구출하기 위해서 우주선을 만들고 있다.

우주선을 만들기 위해서는 총 N개의 부품을 상점에서 모두 구입해야 한다. 모든 부품은 무게 W와 에너지 E를 갖고 있다. 상점에서는 모든 부품을 1부터 N번까지 부품을 순서대로 나열해놓고 판매하고 있다.

이 상점에서는 특이하게도 부품의 가격을 W x E의 비용으로 팔고 있다. 상점에서는 또한 특이한 방식의 판매를 하는데, L 부품부터 R 부품중 최대 무게 W_max 와 최대 에너지 E_max의 곱 W_max * E_max의 비용을 지불한다면 L부터 R사이의 모든 부품을 한번에 구입할 수 있다. 또한 이 상점은 X부품과 Y부품 (X<Y)을 동시에 구입하거나 X부품을 Y부품 보다 먼저 구입할 순 있지만, Y부품을 X부품보다 먼저 구입할 순 없다.

그렇다면 스타로드와 토끼가 모든 부품을 살 수 있는 최소의 비용을 구해보도록 하자.

입력

첫 번째 줄에는 부품의 개수 N(1 ≤ N ≤ 1,000)가 주어진다.

두 번째 줄에는 각 부품의 무게 W(0 ≤ W ≤ 1,000,000)가 주어진다.

세 번째 줄에는 각 부품의 에너지 E(0 ≤ E ≤ 1,000,000)가 주어진다.

출력

스타로드와 토끼가 모든 부품을 살 수 있는 최소비용을 한줄에 출력하라.

문제 풀이

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, Weight[], Energy[];
    static long maxBoard[][], dp[][];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15912_우주선만들기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        Weight = new int[N];
        Energy = new int[N];
        dp = new long[N][N];
        maxBoard = new long[N][N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            Weight[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            Energy[i] = Integer.parseInt(st.nextToken());
        }

        long maxW=0, maxE=0;
        for (int i = 0; i < N; i++) {
            maxW = Weight[i];
            maxE = Energy[i];
            for (int j = i; j < N; j++) {
                maxW = Math.max(maxW, Weight[j]);
                maxE = Math.max(maxE, Energy[j]);
                maxBoard[i][j] = maxW * maxE;
                if(i == j) dp[i][j] = maxBoard[i][j];
            }
        }

        for(int len=2; len<=N; len++) {
            for(int start=0; start<=N-len; start++) {
                int end = start+len-1;
                dp[start][end] = maxBoard[start][end]; // 한번에 구매
                for(int idx=start; idx<end; idx++) {
                    dp[start][end] = Math.min(dp[start][end], dp[start][idx] + dp[idx+1][end]); // 분할구매
                }
            }
        }

        bw.write(String.valueOf(dp[0][N-1]));
        bw.flush();
        bw.close();
        br.close();
    }
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N;
    cin >> N;
    vector<long long> W(N + 1), E(N + 1), dp(N + 1);

    for (int i = 1; i <= N; i++) {
        cin >> W[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> E[i];
    }

    for (int i = 1; i <= N; i++) {
        dp[i] = LLONG_MAX;
        long long maxW = 0, maxE = 0;
        for (int j = i; j >= 1; j--) {
            maxW = max(maxW, W[j]);
            maxE = max(maxE, E[j]);
            dp[i] = min(dp[j - 1] + maxW * maxE, dp[i]);
        }
    }

    cout << dp[N] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}