[백준] 1082 방 번호 (자바 풀이)

문제

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

1082번: 방 번호

풀이

숫자를 사서 가장 큰 숫자를 만드려면 어떻게 해야 할까? 아래와 같은 우선순위를 고려해야 할 것이다.

 

1. 자릿수를 가장 길게 만든다.

2. 맨 앞자리부터 가장 큰 수가 들어가야 한다.

 

따라서 우선 가장 저렴한 숫자를 최대한 많이 사서 자릿수를 최대한 길게 만든다. 

이때 가장 저렴한 숫자가 0이라면, 두 번째로 저렴한 숫자를 맨 앞에 두고 이후 0을 최대한 많이 사서 붙인다.

자릿수를 가장 길게 만들었다면 맨 앞 숫자에서부터 큰 숫자로 교체를 시도한다.

큰 숫자로 교체를 시도한다는 것은, 기존에 있던 숫자의 비용을 돌려받은 후 큰 숫자의 비용을 지불할 수 있다면 교체가 가능한 것이다.

 

예시를 들어보자.

 

3

6 7 8

21 

의 경우 아래와 같이 진행된다.

 

step 1

가장 싼 숫자는 0이다. 따라서 두 번째로 저렴한 숫자 1을 맨 앞에 두고 0을 최대한 많이 둔다.

ans : 1 0 0 , cost = 19 ( 7+6+6 )

step 2

앞에서부터 큰 숫자로 교체를 시도한다. 맨 앞의 숫자 1의 비용은 7원이다. 현재까지 든 비용은 19원이다.

그럼 가장 큰 숫자인 2부터 교체가 가능한지 확인한다. 숫자 2의 비용은 8원이다.

이때 19-7+8 = 20 < 21(M) 이므로 교체가 가능하다.

ans : 2 0 0 , cost = 20

step 3

두 번째 숫자의 교체를 시도한다. 두 번째 숫자 0의 비용은 6원이다. 현재까지 든 비용은 20원이다.

가장 큰 숫자인 2부터 교체가 가능한지 확인한다. 숫자 2의 비용은 8원이다.

20-6+8 = 22 > 21(M) 이므로 2로는 교체가 불가능하다.

두번째로 큰 숫자인 1로 교체가 가능한지 확인한다. 숫자 1의 비용은 7원이다.

20-6+7 = 21 <= 21(M) 이므로 1로 교체가 가능하다.

ans : 2 1 0 , cost = 21

step 4

마지막 숫자의 교체를 시도한다. 마지막 숫자 0의 비용은 6원이다. 현재까지 든 비용은 21원이다.

가장 큰 숫자인 2부터 교체가 가능한지 확인한다. 숫자 2의 비용은 8원이다.

21-6+8 = 23 > 21(M) 이므로 2로는 교체가 불가능하다.

두번째로 큰 숫자인 1로 교체가 가능한지 확인한다. 숫자 1의 비용은 7원이다.

21-6+7 = 22 > 21(M) 이므로 1로 교체가 불가능하다.

 

따라서 마지막 숫자는 교체가 불가능하다.

최종 결과는 210이다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int P[];
    static int N, M;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        P = new int[N];
        for(int i=0; i<N; i++) {
            P[i] = sc.nextInt();
        }
        M = sc.nextInt();
        int ans[] = new int[100];
        int cost = 0;
        int idx = 0;
        /* 가장 싼 숫자로 가장 긴 자릿수 만들기 */
        int minIdx = findMin(0);
        if(minIdx == 0) {    // 0이 가장 싼 값이라면
            minIdx = findMin(1);
            if(P[minIdx] <= M) {    // 두번째로 싼 숫자를 살 수 있다면 가장 앞에 넣어줌
                ans[idx++] = minIdx;
                cost += P[minIdx];
                minIdx = 0;
            }else {    // 두번째로 싼 숫자를 살 수 없다면
                System.out.println(0);
                return;
            }
        }
        while(cost+P[minIdx] <= M) {
            ans[idx++] = minIdx;
            cost += P[minIdx];
        }
        
        /* 가장 앞에서부터 큰 숫자로 교체 시도*/
        for(int i=0; i<idx; i++) {
            for(int j=N-1; j>=0; j--) {
                if(cost-P[ans[i]]+P[j] <= M) {
                    cost = cost-P[ans[i]]+P[j];
                    ans[i] = j;
                    break;
                }
            }
        }
        
        for(int i=0; i<idx; i++) {
            System.out.print(ans[i]);
        }
 
    }
    
    public static int findMin(int start) {
        int retIdx=0, min=100;
        for(int i=start; i<N; i++) {
            if(min > P[i]) {
                min = P[i];
                retIdx = i;
            }
        }
        
        return retIdx;
    }
 
}

결과