[백준] 1082번 : 방 번호 Gold3(골드3) - JAVA[자바]

[Gold III] 방 번호 - 1082

문제 링크

성능 요약

메모리: 16908 KB, 시간: 108 ms

분류

다이나믹 프로그래밍, 그리디 알고리즘

제출 일자

2024년 6월 13일 21:31:52

문제 설명

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 P_i이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P₀ = 6, P₁ = 7, P₂ = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P₀, ..., P_N-1이 주어진다. 마지막 줄에는 M이 주어진다.

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

 

접근 방법

1. 값을 가장 길게 만드는게 목표

2. 가장 길게 만들 수 있는 길이가 같을 때 가장 큰 값을 만들어줘야한다.

3. 디피를 길이순으로 진행하면 된다.

4. 길이는 최대50글자이기 때문에 문자열로 진행한다.

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

/**
 * 문제: BOJ_1082_방번호
 * 메모리: 16908KB
 * 시간: 108ms
 * 접근 방법
 * 1. 값을 가장 길게 만드는게 목표다.
 * 2. 가장 길게 만드는 길이가 같다면 가장 크게 만들어야 한다.
 * 3. DP를 길이순으로 진행할 수 있도록 한다.
 * 4. 길이는 최대 50자리 임으로 문자열로 진행해준다.
 */
public class Main {
    static final String EMPTY = "";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] prices = new int[N];

        // Input
        int size = 51;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            prices[i] = Integer.parseInt(st.nextToken());
            if (size > prices[i]) {
                size = prices[i];
            }
        }// Input End

        int M = Integer.parseInt(br.readLine());

        // 공백으로 초기화
        size = (M / size);
        String[][] dp = new String[size + 1][M + 1];
        for (int i = 0; i <= size; i++) {
            for (int j = 0; j <= M; j++) {
                dp[i][j] = EMPTY;
            }
        }

        // 길이는 1부터 size까지
        for (int i = 1; i <= size; i++) {
            for (int j = 0; j < N; j++) {
                // 첫번째는 제외
                if(i == 1 && j == 0) continue;

                int spend = prices[j];
                for (int k = spend; k <= M; k++) {
                    // j가 0일 때 이전 값이 빈 값이면 넘어간다.
                    if (j == 0 && dp[i - 1][k].equals(EMPTY)) {
                        continue;
                    }

                    // 새로운 값이 더 길이가 길거나 더 큰값이라면 적용
                    String newValue = dp[i - 1][k] + j;
                    if (isBig(dp[i][k - spend], newValue)) {
                        dp[i][k - spend] = newValue;
                    }
                }
            }
        }

        String answer = EMPTY;
        for (int j = 0; j <= M; j++) {
            if (isBig(answer, dp[size][j])) {
                answer = dp[size][j];
            }
        }

        System.out.println(answer.equals(EMPTY) ? 0 : answer);
    }

    // 더 큰 값 리턴
    private static boolean isBig(String prevValue, String newValue) {
        int prevLen = prevValue.length();
        int newLen = newValue.length();
        if (prevLen > newLen) return false;
        else if (prevLen < newLen) return true;
        else {
            return newValue.compareTo(prevValue) > 0;
        }
    }
}