[AtCoder] Addition and Multiplication2

https://atcoder.jp/contests/abc257/tasks/abc257_e

E - Addition and Multiplication 2

뭔가 쉬워보였으나 마음처럼 쉽게 풀리지 않은 문제였다.

$x$가 10의 자리 단위로 커지니 최대한 큰 수부터 앞자리에 넣는 것이 유리하다는 생각을 하여서 C 배열의 뒷자리부터 확인하며 $x$를 만들어나갔다. 정말 간단한 Greedy 문제라고 생각했다. 하지만 그렇지 않았다..

 

아무리 앞에 큰 9를 넣는다한들 결과적으로 자릿수가 모자르게 되면 그보다 작은 수가 되기 때문에 $x$의 자릿수도 생각을 해야 했다.

그래서 최대한의 길이를 연산한 뒤, 이를 초기값으로 설정한다.

 

그리디하게 앞 숫자부터 뒤 숫자로 이동해가며 숫자를 교체한다. 이 때 C가 비내림차순이 아니라면, 비내림차순의 C를 생성한다.

 

[원문]

If $x$ is viewed as a string of its base 10 representation without leading zeros, the operation is simply appending digit $i$ to the end of it. Assume array $C$ is non-decreasing. To maximize $x$, you want to first make it as long as possible, therefore its length is $l = \lfloor\frac{N}{C_1}\rfloor$

 

You can then initialize an array of $l$ ones, and keep track of the money you have left. Greedily increase the digits from the most significant (left) to the least (right) as long as you have money to cover the cost increases.

 

For the case that $C$ is not non-decreasing, you can simply set $C'_i := minC_{i...9}$, it's not possible to get "stuck" on an invalid value as the cost increase would be zero at that point.

 

 

추가로, i 와 j를 잘못 보기 시작하면 시간을 너무 많이 날린다..주의하자 🚨

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<int> cost(10);
int main() {
    int n;
    string x = "";
    cin >> n;
    for(int i = 1;i < 10;i++) {
        cin >> cost[i];
    }
    // c1 ~ c9까지 최소의 cost 찾기
    int mn = *min_element(cost.begin() + 1, cost.end());
    int length = n / mn;
    // 앞자리부터 변경
    for(int i = 0;i < length;i++) {
        for(int j = 9;j >= 1;j--) {
            if((long long) mn * (length - 1 - i) + cost[j] <= n) {
                n -= cost[j];
                x.push_back((char)('0' + j));
                // i번째 자릿수 교체 완료
                break;
            }
        }
    }
    
    cout << x << '\n';
    return 0;
}