[백준] 1082번 방 번호 (gold 3

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.valueOf(br.readLine());

        //번호마다의 가격 저장.
        int[] num=new int[n];
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            num[i]=Integer.valueOf(st.nextToken());
        }

        //사용할 수 있는 총 금액.
        int m=Integer.valueOf(br.readLine());
        String[] make=new String[m+1];
        for(int i=n-1; i>=0; i--) {
            //가격
            int value=num[i];
            for (int j = 1; j <= m; j++) {
                //비어있지 않는 경우에 추가하는 게 보통이지만,
                //해당 인덱스가 value와 동일하면 넣을 수 있다.
                if(make[j]==null && j==value){
                    make[j]=String.valueOf(i);
                }
                //만약 해당 가격이 비어 있지 않은 경우. 그리고 해당 인덱스 +value<=m일때

                if(make[j]!=null && j+value<=m){
                    //인덱스+value가 null이면, 그냥 집어넣기
                    if(make[j+value]==null){
                        make[j+value]=make[j]+i;
                    }
                    //null이 아니면. 인덱스+value와 , 현재 인덱스에 추가한 것 비교하여 추가.
                    else{
                        String temp=com(make[j+value], make[j]+i);
                        make[j+value]=temp;
                    }
                }

            }
        }

        String big="0";
        for(int i=1; i<=m; i++){
            if(make[i]==null){
                continue;
            }
            big= com(big, make[i]);
        }
        bw.write(big);
        bw.flush();

    }
    //최대 50개의 숫자의 길이이므로, long범위도 초과.
    //string으로 숫자를 다룰때. 이들의 대소비교.
    public static String com(String a, String b) {
        //만약, 00000이면 "0"으로 바꾸어서 계산;
        if(zero(a)){
            a="0";
        }
        if(zero(b)){
            b="0";
        }

        if(a.length()>b.length()){
            return a;
        }
        else if(a.length()==b.length()){
            boolean is=a.compareTo(b) < 0 ? true : false;
            if(is){
                return b;
            }
            else{
                return a;
            }
        }
        else{
            return b;
        }
    }
    //이게 0인지 아닌지, 0이면 "0"으로 아니면 a 그대로.
    public static boolean zero(String a){
        boolean zero=true;
        for(int i=0; i<a.length(); i++ ){
            if(a.charAt(i)!='0'){
                zero=false;
            }
        }
        if(zero){
            return true;
        }
        else{
            return false;
        }
    }
}