[백준] 21549 - Московские числа (c++)

Russian Olympiad in Informatics > Russian Olympiad in Informatics 2021 5번 문제이다.

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

 

문제 요약

로마 숫자와 비슷한 모스크바 숫자를 만들려고 한다. 모스크바 숫자의 각 자릿수는 알파벳으로 이루어져 있고 각 자릿수에 해당하는 값은 다음과 같다.

 

숫자의 값은 각 자릿수 기여값의 합이다. 각 자릿수의 기여값은 오른쪽에 더 큰 값이 없으면 (+자릿수값)이고 있으면 (-자릿수값)이다. 테스트케이스 마다 대문자 알파벳과 ?가 조합된 문자열이 주어질 때 ?자리의 올 알파벳을 결정하여 최대값을 만들고 숫자의 값과 완성된 문자열을 출력해라. *문자열의 총 길이는 300,000을 넘지 않는다.

 

풀이 (N)

• DP

dp[i][j]를 i번째 자리까지 알파벳을 최대 j까지 사용했을 때 최댓값으로 정의한다. ?는 무조건 j로 채우는게 최적이고 dp[i][j]는 dp[i-1][0]~dp[i-1][j]에서 갱신 될 수 있기 때문에 s[i]=='?'일땐 dp[i][j] = max(dp[i-1][0]~dp[i-1][j]) +num[j] 이고 아닐 땐 j가 s[i] 보다 클 때만 dp[i][j]= max(dp[i-1][0]~dp[i-1][j]) +num[s[i]]*(j==s[i]?1:-1)가 된다. 나머지 경우는 정의에 어긋나기 때문에 -INF로 채운다. N*(26^2)으로 풀 수도 있지만 dp를 채우는 과정에서 mx를 관리해주면 N*26으로 줄일 수 있다.

복원하는 건 dp[i][j]가 max(dp[i-1][0]~dp[i-1][j])에서 왔다는 걸 알기 때문에 dp[n]의 최대값 인덱스 부터 시작해서 하나 씩 되돌려주면 된다.

 

편의를 위해 문자열을 뒤집고 앞에 _를 붙였다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e18;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    vector<ll> num;
    for(ll i=0,j=1;i<13;i++,j*=10) 
        num.push_back(j),num.push_back(j*5);

    int t;cin >> t;
    while(t--) {
        string s;cin>>s;
        int n=s.size();
        s.push_back('_');
        reverse(s.begin(),s.end());

        vector<array<ll,26>> dp(n+1);
        for(int i=1;i<=n;i++) {
            dp[i].fill(-INF);
            ll mx =-INF;
            for(int j=0;j<26;j++) {
                mx=max(mx,dp[i-1][j]);
                if(s[i]=='?') 
                    dp[i][j]=mx+num[j];
                else if(j>=s[i]-'A')
                    dp[i][j]=mx+num[s[i]-'A']*(j==s[i]-'A'?1:-1);
            }
        }
        auto st =max_element(dp[n].begin(),dp[n].end());
        for (int i=n,idx=st-dp[i].begin(); i>=1; i--) {
			if(s[i]=='?') s[i]=idx+'A';
			idx=max_element(dp[i-1].begin(), dp[i-1].begin()+idx+1)-dp[i-1].begin();
		}
        reverse(s.begin(),s.end());
        s.pop_back();
        cout << *st << '\n'<<s <<'\n';
    }
}