백준 17828번: 문자열 화폐 (Python/Java)

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

17828번: 문자열 화폐

 

 

 

접근

---

사전 순으로 가장 빠른 문자열을 구하라는 말은 A부터 Z까지 순서대로 문자가 들어가야 한다는 뜻이다. 하지만 문자열 길이는 정해져 있고, 가장 처음에 A 하나 넣고 그 뒤에 조합될 수 있는 모든 경우의 수를 비교하기에는 연산이 비상식적으로 늘어날 것이 분명하다. 때문에 조금 더 과감해졌다. 모든 문자열을 A로 채워 넣었다.

 

예시를 살펴보자. 만일 길이가 5인 문자열을 통해 가치를 7로 만들어야 한다고 생각해보자. 이 경우 AAABB와 AAAAC, 두 가지 경우의 수가 나올 것이다. 이 중 사전 순으로 빠른 것은 AAAAC다. 만일 길이 5, 가치 7인 문자열을 출력하라고 한다면 AAAAC를 출력해야 할 것이다. 이제 풀이 방법을 살펴보자. 나는 우선 모든 문자열을 A로 채워 넣었다. 즉, 맨 처음 문자열은 AAAAA다. 이제 Z부터 B까지 들어갈 수 있는 문자열을 역순으로 탐색했다. (A는 탐색할 필요 없다. 이미 모든 문자열은 A로 채워져 있기 때문이다.)

 

Z부터 D까지는 문자열에 넣을 수 없다. 문자의 가치가 최종적으로 나와야 하는 가치보다 크거나(Z의 경우 가치가 26인데 전체 가치가 7이 되어야 하기 때문에 넣을 수 없다) 문자를 넣었을 때 전체 문자열을 맞출 수 없기 때문이다.(D의 경우 가치는 4여서 전체 가치를 7로 맞출 수는 있지만 그 경우에는 전체 문자열을 5로 맞출 수 없다)

 

이제 C를 탐색해보자. 전체 문자열을 5로 맞추면서 7의 가치를 만들기 위해서는 C를 한 개 넣고 A를 4개 넣으면 된다. 이미 문자열에는 5의 A가 있으니 A의 개수를 하나 빼주고 C 하나 개수를 늘려준다. 그렇게 하면 AAAAC 문자열을 만들 수 있고, 전체 가치는 7로 딱 맞아떨어진다.

 

이와 같은 방법으로 B를 두 개 넣을 수 있다. 이때는 A 개수를 두 개 빼주고 B 개수를 두 개 늘려주면 된다. 이때 나오는 문자열은 AAABB다. 하지만 이럴 경우에는 사전 순으로 AAAAC보다 늦다. 즉, 해당 문자를 넣었을 때 나오는 전체 가치가 목표 가치와 같으면 그 문자열은 무조건 사전 순으로 가장 빠른 문자열이다. 그 뒤 탐색은 굳이 하지 않아도 된다.

 

덧붙여 맨 처음 설정했던 A의 개수는 문자열 전체 길이와 같다. 때문에 A의 개수가 음수로 넘어간다면 그것은 추가한 문자열이 목표 문자열 개수보다 많은 개수의 문자를 추가했다는 뜻이 된다. 즉, A의 개수가 음수라면 !를 출력해줘야 한다.

 

 

 

풀이

---

Python

roundNum, goalNum = map(int, input().split())

board = [0 for i in range(27)]
resultNum = 0

board[1] = roundNum
resultNum = roundNum

for i in range(26, 1, -1):
    thisNum = (goalNum-resultNum)//(i-1)

    if thisNum > 0:
        resultNum = (resultNum - thisNum) + (i*thisNum)
        board[1] -= thisNum
        board[i] += thisNum
    
result = ""
for i in range(27):
    if board[i] != 0:
        result += chr(i+64)*board[i]

if resultNum == goalNum and board[1] >= 0:
    print(result)
else:
    print("!")

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int roundNum = Integer.parseInt(firstLine[0]), goalNum = Integer.parseInt(firstLine[1]);

        int[] board = new int[27];
        board[1] = roundNum;
        int resultNum = roundNum;

        for(int i = 26 ; i > 1 ; i--){
            int thisNum = (goalNum-resultNum)/(i-1);
            if(thisNum > 0){
                resultNum = (resultNum - thisNum) + (i*thisNum);
                board[1] -= thisNum;
                board[i] += thisNum;
            }
        }

        StringBuilder result = new StringBuilder();
        for(int i = 0 ; i < 27 ; i++){
            if(board[i] != 0){
                for(int j = 0 ; j < board[i] ; j++){
                    result.append(Character.toString((char)(i+64)));
                }
            }
        }

        if(resultNum == goalNum && board[1] >= 0){
            System.out.println(result);
        }else{
            System.out.println("!");
        }
    }

}