백준(1082번) - 방 번호(Java) (그리디, DP)

 DP와 그리디가 섞인 문제이다.

 

처음에는 뒷 숫자부터 무작정 앞으로 갖다 붙이면 될 줄 알았다.

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


public class Main
{
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] price = new int[n];
		for(int i = 0 ; i < n ; i++)
		{
			price[i] = Integer.parseInt(st.nextToken());
		}
		
		int m = Integer.parseInt(br.readLine());
		StringBuilder ans = new StringBuilder();
		int index = n-1;
		
		while(index >= 0)
		{
			if(price[index] > m)
			{
				index--;
			}
			else
			{
				ans.append(index);
				m -= price[index];
			}
		}
		
		System.out.println(ans);
	}

}

 뭔 이런 간단한 문제가 다 있나 라는 거만한 마인드로 했다가 대차게 까였다.

---

 그래서 DP적(?)으로 생각해 각 금액에서 만들 수 있는 최댓값의 번호판을 찾는 방식으로 해결했다.

 

3
6 7 8
21

이 1번의 케이스로 설명을 하자면

 

< 6원 0 / 7원 1 / 8원 2 > 이렇게 만들 수 있다는 건 바로 안다.

이걸 최대 21원까지 생각해 준다면

12원 00

13원 01 / 10 (큰 숫자인 10을 살린다.)

14원 11 / 02 / 20 (큰 숫자인 20을 살린다.)

 

이런 식으로 각 금액에서 만들 수 있는 조합을 전부 생각하고 그중 최강의 숫자만 살려 또 번호를 뒤에 붙이고 또 최강만 남기고...

이것의 반복으로 작성해 봤다.

<문제>

https://www.acmicpc.net/problem/1082

1082번: 방 번호

---

<소스코드>

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


public class Main
{
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] price = new int[n];
		for(int i = 0 ; i < n ; i++)
		{
			price[i] = Integer.parseInt(st.nextToken());
		}
		
		int m = Integer.parseInt(br.readLine());

		String[] dp = new String[m+1];	//dp의 인덱스를 m(총 금액)으로 세팅한다.
		String ans = "0";
		Arrays.fill(dp, "-1");	//초기값 -1으로 세팅 (세팅 없을 시 null 그러면 골치가 살짝 아파짐)
		
		for(int i = 0 ; i < n ; i++)
		{
			if(price[i] > m) continue;
			
			//일단 초기에 price[i](금액)으로 맞출 수 있는 번호 넣기
			dp[price[i]] = Integer.toString(i);	
		}
		
		for(int i = 0 ; i <= m ; i++)
		{
			if(dp[i] != "-1")	//"-1"은 쓰레기 값으로 무시
			{
				for(int j = 0 ; j < n ; j++)
				{
					if(i + price[j] <= m) //허용 금액 초과하지 않는 선에서
					{
						//만들 수 있는 번호의 조합
						String newString = dp[i] + Integer.toString(j);
                        
						BigInteger num1 = new BigInteger(newString);
						BigInteger num2 = new BigInteger(dp[i + price[j]]);
			
						//9가 50개 들어갈 수 있어서 문자열로 선언했지만 비교는 숫자로 해줘야하는...
						int result = num1.compareTo(num2);
                        
						if(result > 0) 
						{
							//만들 수 있는 숫자가 기존 숫자보다 큰 경우 스위칭
							dp[i + price[j]] = newString;
						}
					}
				}
			}
		}
		
		for(String s : dp)	//다 뒤져보면서 최상의 경우의 수 선택
		{
			BigInteger num1 = new BigInteger(s);
			BigInteger num2 = new BigInteger(ans);
			
			int result = num1.compareTo(num2);
			
			if(result > 0)
				ans = s;
		}
		
		System.out.println(ans);
	}

}