백준 1082, 방 번호 - DP, Greedy, 문자열
https://www.acmicpc.net/problem/1082
1. 아이디어
1) DP 배열 정의: String[] dp
-
dp[cost]
:cost
원 금액 내로 만들 수 있는 최대 숫자 문자열 -
출력, 최대 숫자:
BigInteger(dp[m])
=>dp[]
원소에 Leading-Zero 문자열이 저장될 수 있으므로,
BigInteger
를 이용하여 Leading-Zero 문자열을 제거
BigInteger 클래스
int
,long
범위를 넘어가는 매우 큰 정수를 사용, 비교해야 할 때 활용
=> 문자열에 정수를 담아서 처리- "001"과 같은 Leading-Zero로 표현된 정수에서 Leading-Zero 제거 가능
=> Leading-Zero 가 포함된 정수 문자열을BigInteger
에 담은 후,toString()
메소드 호출
2) 규칙 및 점화식
-
초기식: 입력
costs[]
의 각 원소cost
에 대해,dp[cost] = String(i)
-
1원 ~ m원 까지 각 금액 내로 만들 수 있는 최대 숫자 문자열로
dp[]
채우기 -
dp[totalCost] = max(dp[totalCost], dp[totalCost - cost] + String(i))
dp[totalCost - cost] + String(i)
:totalCost
금액에서cost
금액에 해당하는 숫자String(i)
를 새로 구입하여, 이어붙임
2. 자료구조
String[] dp
: DP 배열
int[] dp
,long[] dp
사용 못하는 이유
- 자료형:
dp[]
의 원소가 최대 9999...999 (숫자 9가 50개) 이므로,
정수 자료형은 스택 오버플로우 발생
3. 시간 복잡도
- DP 배열 채우기: O(n x m)
=> n, m 최대값 대입: 10 x 50 = 500 << 2억
코드
import java.io.*;
import java.util.StringTokenizer;
import java.math.BigInteger;
public class Main_BigInteger {
static int n; // 0 ~ (n-1) 방 번호 숫자
static int[] costs; // 각 방 번호 숫자의 비용
static int m; // 전체 보유 금액
static String maxNumStr;
static String[] dp;
static String[] digitStr = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
static String getMaxStr(String str1, String str2) {
if (str1 == null)
return str2;
if (str2 == null)
return str1;
BigInteger b1 = new BigInteger(str1);
BigInteger b2 = new BigInteger(str2);
return b1.compareTo(b2) > 0 ? str1 : str2;
}
static void solution() {
// 초기식: 입력 cost 금액에 해당하는 숫자로 dp[cost] ~ dp[m] 초기화
for (int i = 0; i < n; i++) {
for (int totalCost = costs[i]; totalCost <= m; totalCost++)
dp[totalCost] = getMaxStr(dp[totalCost], digitStr[i]);
}
// DP 채우기: totalCost 금액 내로 만들 수 있는 최대 숫자
for (int totalCost = 1; totalCost <= m; totalCost++) {
for (int i = 0; i < n; i++) {
int cost = costs[i];
if (totalCost < cost) // totalCost 금액으로 못 사는 경우 (돈 부족)
continue;
if (dp[totalCost - cost] == null)
continue;
dp[totalCost] = getMaxStr(
dp[totalCost], dp[totalCost - cost] + dp[cost]
);
}
}
// dp[m]에 Leading-Zero 존재할 수 도 있음
// dp[m] -> BigInteger -> String 으로 변환하여, Leading-Zero 문자열 제거
BigInteger b = new BigInteger(dp[m]);
maxNumStr = b.toString();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
costs = new int[n];
for (int i = 0; i < n; i++)
costs[i] = Integer.parseInt(st.nextToken());
m = Integer.parseInt(br.readLine());
dp = new String[m + 1];
solution();
System.out.println(maxNumStr);
}
}
Author And Source
이 문제에 관하여(백준 1082, 방 번호 - DP, Greedy, 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-1082-방-번호-DP저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)