[JAVA] 백준 1082 방 번호

오늘의 문제 : https://www.acmicpc.net/problem/1082

 

분명 하루 딱 한 문제만 푸는데 이렇게 어려울 수가.. 요즘 다시 알고리즘의 절망 계곡에 들어선 것 같습니다. 

x축을 전문가를 살짝 아는 사람으로 바꿔서 읽어주세요

 

제 자심감의 봉우리는 너무 금방올라가서 탈입니다. 아는 것이 힘이지만, 살짝 아는 것은 고통이군요.

 

문제 풀겠습니다.

 

처음 접근은 그리디로 했으나, 조건을 코드로 구현하는 것이 어려워서 다이내믹 프로그래밍을 사용하여 풀었습니다. 

 

저는 사용한 비용을 통하여 점화식을 세웠습니다.

 

DP[n] =  Math.max(DP [n] , DP [n - 사용가능 한 비용] + 사용한 숫자(String)..)

 

사용가능 한 비용이 최대 n개가 되지만, 문제 조건을 보면 최대 비용이 50이라 그냥 했습니다.

 

그리고 이제 사용가능 한 비용에 따른 문자들을 비교해 줘야 했습니다. (50 자리라서 문자열 비교)

 

문자열 비교 메서드가 좀 지져분한데, 이건 미리 생각 안 하고 막 쳐서 그렇습니다.  그러지 맙시다

 

-코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Num1082방_번호 {
    private static class Pair{
        int num;
        int cost;
        Pair(int num,int cost){
            this.num = num;
            this.cost = cost;
        }
    }
    static int[] arr;
    static int n, totalCost;
    static String[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr= new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        totalCost = Integer.parseInt(br.readLine());
        dp = new String[51];
        Arrays.fill(dp,"");
        for(int i=0;i<n;i++){
            int cost = Integer.parseInt(st.nextToken());
            arr[i] = cost;
//            dp[cost] = String.valueOf(i);
        }
        find(totalCost,n-1);
        System.out.println(dp[totalCost]);
    }
    public static String find(int cost,int start){
        if(cost <= 0 ) return "";
        if(!dp[cost].isEmpty()) return dp[cost];
        for(int i = start;i>=0;i--){
            if(cost - arr[i] >= 0 ){
                if(dp[cost].isEmpty() && i==0){
                    dp[cost] ="0";
                }else{
                    dp[cost] = compare(dp[cost],find(cost-arr[i],start),String.valueOf(i));
                }
                dp[cost] = compare(dp[cost],find(cost,start-1),"");
            }
//            System.out.println(Arrays.toString(dp));
        }
        return dp[cost];
    }
    public static String compare(String o1, String o2, String o3) {
        StringBuilder sb = new StringBuilder();
        if (o2.length() == o3.length()) {
            if (o2.charAt(0) > o3.charAt(0)) {
                sb.append(o2).append(o3);
            } else {
                sb.append(o3).append(o2);
            }
        } else if (o3.isEmpty()){
            sb.append(o2);
        }else{
            for(int i=0;i<o2.length();i++){
                if(o2.charAt(i) <= o3.charAt(0)){
                    sb.append(o2, 0, i).append(o3).append(o2.substring(i));
                    break;
                }
            }
        }
        String str = sb.toString();
        if(str.length()>1){
            while(str.charAt(0) == '0'){
                str = str.replaceFirst("0","");
                if(str.isEmpty()) return o1;
            }
        }
        if(o2.isEmpty()) str = o3;
//        System.out.println(o1+" "+str);
        if(str.isEmpty()) return o1;
        if(o1.isEmpty()) return str;
        if(o1.length() > str.length()){
            return o1;
        }else if(o1.length() < str.length()){
            return str;
        }
        for(int i=0;i<o1.length();i++){
            if(o1.charAt(i) > str.charAt(i)) return o1;
            if(o1.charAt(i) < str.charAt(i)) return str;
        }
        return o1;
    }
}

 

후기

 

그리디 풀이

 

1. 가장 싼 번호를 찾아서 최대한 긴 숫자를 만든다.

2. 그렇게 만든 숫자의 맨 앞자리부터 각 자리를 다른 더 큰 숫자로 바꿀 수 있는지 확인한다.

3. 바꿀 수 있다면 숫자를 바꾸고 비용을 추가한다. 

4. 반복