👨💻 문제
스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다.
방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다.
숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다.
문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다.
방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다.
최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.
⌨️ 입력
첫째 줄에 N이 주아진다.
둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다.
마지막 줄에는 M이 주어진다.
🖨️ 출력
첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다.
적어도 하나의 숫자를 살 수 있는 입력만 주어진다.
📖 예제
입력
3 6 7 8 21출력
210
✍️ 풀이
⌨️ 데이터 입력
private static int n, money;
private static int[] pricePerNumber;
private static int[] maxNumber;
private static void input() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
pricePerNumber = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
pricePerNumber[i] = Integer.parseInt(st.nextToken());
}
money = Integer.parseInt(br.readLine());
}n : 문방구에서 파는 숫자의 수
money : 잔여 금액
pricePerNumber : 숫자(인덱스) 별 가격
maxNumber : 만들 수 있는 가장 큰 방 번호, 결과값
🐍 만들 수 있는 가장 긴 숫자 만들기
private static void makeMaxLengthNumber() throws AnswerIsZero{
if(n == 1){
throw new AnswerIsZero();
}
int cheapestNumberExcludeZero = getCheapestNumberExcludeZero();
int cheapestNumberExcludeZeroPrice = pricePerNumber[cheapestNumberExcludeZero];
int cheapestNumberIncludeZero = getCheapestNumberIncludeZero(cheapestNumberExcludeZero);
int cheapestNumberIncludeZeroPrice = pricePerNumber[cheapestNumberIncludeZero];
if(money < cheapestNumberExcludeZeroPrice){
throw new AnswerIsZero();
}
money -= cheapestNumberExcludeZeroPrice;
int length = 1;
length += money / cheapestNumberIncludeZeroPrice;
money %= cheapestNumberIncludeZeroPrice;
maxNumber = new int[length];
Arrays.fill(maxNumber, cheapestNumberIncludeZero);
maxNumber[0] = cheapestNumberExcludeZero;
}가장 큰 숫자를 만들기 위해 우선 가장 긴 숫자를 만들어야 한다.
가격이 가장 저렴한 숫자들로 최대한 긴 숫자를 만들어낸다.
📍 0을 제외한 가장 저렴한 수
private static int getCheapestNumberExcludeZero(){
int cheapestNumber = -1;
int cheapestPrice = Integer.MAX_VALUE;
for(int i=n-1; i>0; i--){
if(pricePerNumber[i] < cheapestPrice){
cheapestNumber = i;
cheapestPrice = pricePerNumber[i];
}
}
return cheapestNumber;
}첫 숫자는 0이어선 안 된다.
0이 아닌 가장 저렴한 숫자를 하나 정한다.
📍 0을 포함한 가장 저렴한 수
private static int getCheapestNumberIncludeZero(int cheapestNumberExcludeZero){
return pricePerNumber[0] < pricePerNumber[cheapestNumberExcludeZero] ? 0 : cheapestNumberExcludeZero;
}첫 숫자 이외에는 0이어도 상관없다.
가장 저렴한 숫자를 정한다.
📍 가장 긴 숫자 만들기
money -= cheapestNumberExcludeZeroPrice;
int length = 1;
length += money / cheapestNumberIncludeZeroPrice;
money %= cheapestNumberIncludeZeroPrice;
maxNumber = new int[length];
Arrays.fill(maxNumber, cheapestNumberIncludeZero);
maxNumber[0] = cheapestNumberExcludeZero;0을 제외한 가장 저렴한 수를 A라 칭하고,
0을 포함한 가장 저렴한 수를 B라 칭한다면,
ABBBBBBBB... 와 같은 형태의 길이가 가장 긴 숫자를 만들어낼 수 있다.
📍 답이 0인 경우
if(n == 1){
throw new AnswerIsZero();
}n이 1이면 사용할 수 있는 숫자가 0뿐이다.
if(money < cheapestNumberExcludeZeroPrice){
throw new AnswerIsZero();
}0을 제외한 가장 저렴한 수가 잔여 금액보다 비싼 경우이다.
5
1 50 50 50 50
1과 같은 테스트케이스에 적용된다.
try{
makeMaxLengthNumber();
...
}
catch(AnswerIsZero e){
System.out.println(0);
}위와 같은 경우 답은 0이다.
♻️ 더 큰 숫자로 대체
private static void switchNumberBigger(){
int length = maxNumber.length;
for(int index=0; index<length; index++){
int currentNumber = maxNumber[index];
int currentNumberPrice = pricePerNumber[currentNumber];
for(int biggerNumber=n-1; biggerNumber>currentNumber; biggerNumber--){
int biggerNumberPrice = pricePerNumber[biggerNumber];
int switchNumberPrice = biggerNumberPrice - currentNumberPrice;
if(money >= switchNumberPrice){
maxNumber[index] = biggerNumber;
money -= switchNumberPrice;
break;
}
}
}
}맨 앞부터 남은 금액으로 바꿀 수 있는 가장 큰 숫자로 대체한다.
예시)
200000
->
852000📄 전체 소스코드
import java.io.*;
import java.util.*;
public class _1082 {
private static int n, money;
private static int[] pricePerNumber;
private static int[] maxNumber;
private static class AnswerIsZero extends Exception{}
public static void main(String[] args) throws IOException {
input();
try{
makeMaxLengthNumber();
switchNumberBigger();
printMaxNumber();
}
catch(AnswerIsZero e){
System.out.println(0);
}
}
private static void input() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
pricePerNumber = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
pricePerNumber[i] = Integer.parseInt(st.nextToken());
}
money = Integer.parseInt(br.readLine());
}
private static void makeMaxLengthNumber() throws AnswerIsZero{
if(n == 1){
throw new AnswerIsZero();
}
int cheapestNumberExcludeZero = getCheapestNumberExcludeZero();
int cheapestNumberExcludeZeroPrice = pricePerNumber[cheapestNumberExcludeZero];
int cheapestNumberIncludeZero = getCheapestNumberIncludeZero(cheapestNumberExcludeZero);
int cheapestNumberIncludeZeroPrice = pricePerNumber[cheapestNumberIncludeZero];
if(money < cheapestNumberExcludeZeroPrice){
throw new AnswerIsZero();
}
money -= cheapestNumberExcludeZeroPrice;
int length = 1;
length += money / cheapestNumberIncludeZeroPrice;
money %= cheapestNumberIncludeZeroPrice;
maxNumber = new int[length];
Arrays.fill(maxNumber, cheapestNumberIncludeZero);
maxNumber[0] = cheapestNumberExcludeZero;
}
// cheapest & biggest
private static int getCheapestNumberExcludeZero(){
int cheapestNumber = -1;
int cheapestPrice = Integer.MAX_VALUE;
for(int i=n-1; i>0; i--){
if(pricePerNumber[i] < cheapestPrice){
cheapestNumber = i;
cheapestPrice = pricePerNumber[i];
}
}
return cheapestNumber;
}
private static int getCheapestNumberIncludeZero(int cheapestNumberExcludeZero){
return pricePerNumber[0] < pricePerNumber[cheapestNumberExcludeZero] ? 0 : cheapestNumberExcludeZero;
}
private static void switchNumberBigger(){
int length = maxNumber.length;
for(int index=0; index<length; index++){
int currentNumber = maxNumber[index];
int currentNumberPrice = pricePerNumber[currentNumber];
for(int biggerNumber=n-1; biggerNumber>currentNumber; biggerNumber--){
int biggerNumberPrice = pricePerNumber[biggerNumber];
int switchNumberPrice = biggerNumberPrice - currentNumberPrice;
if(money >= switchNumberPrice){
maxNumber[index] = biggerNumber;
money -= switchNumberPrice;
break;
}
}
}
}
private static void printMaxNumber(){
StringBuilder sb = new StringBuilder();
for(int num : maxNumber){
sb.append(num);
}
System.out.println(sb);
}
}
입니다.