BOJ 17828

24 Apr 2020 • ProblemSolving

문자열 화폐

문제출처

문제 해석

  • 정해진 가치를 N개의 화폐로 표현할 수 있는 지 맞추는 문제입니다.
  • 화폐 A~Z까지 각 가치는 1~26입니다.
  • 정확히 N개의 화폐로 주어지는 가치를 만들어야합니다.
  • 만족하는 문자열이 여러개일 경우, 사전순으로 가장 앞서는 것을 출력합니다.
  • 만약 존재하지 않으면 “!”를 출력합니다.

설계(10)

  • 문자열의 길이의 범위가 N <=5x10^6이라서 O(N)에 해결해야 하는 문제 같았습니다.
  • 각 문자열을 26개의 알파벳을 모두 비교하면 시간초과가 날 것 같았습니다.
  • 그래서, 처음에 그리디하게 정해진 가치안에서 만족하는 최대의 가치를 정하는 방식으로 진행하였습니다.
  • X가 26이상인 조건으로 구현하려고 하였지만, 생각해보면 남은 N-1개의 화폐가 최소 A이상은 되어야 하기 때문에 X-N > 26인 조건이 필요하였습니다.
  • 위의 조건에 만족하지 않으면 최소 N-2개의 화폐는 A이어야 하고, 남은 X가치의 화폐를 선택해야합니다.
  • 또한, 불가능한 경우를 생각해보면 최대화폐가치인 26이 N개있는 경우보다 원하는 가치 X가 더 크면 안됩니다.
  • 반대로, 최소화폐를 사는 경우인 1이 N개 있는 경우보다 원하는 가치 X가 더 작으면 안됩니다.

구현(20)

코드
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 5000000
int N,X;

char ans[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> X;
    if (26*N<X || N>X){
        cout << "!\n";
    }
    else{
        while (N--){
            if (X - N>26) {
                X-=26;
                ans[N] ='Z';
            }
            else{
                char tmp = X-N-1 +'A';
                ans[N] = tmp;
                X-= X-N;
            }
        }
        cout << ans <<"\n";
    }
    return 0;
}
디버깅
  • 처음에 ans를 string형으로 해서 화폐를 더해준 후, 마지막에 sort하는 방식으로 했습니다.
  • 이렇게 될 경우, 통과가 되지만 시간복잡도는 O(NlogN)이 됩니다.
  • 애초에 원했던 O(N)이 되게 하기 위해서, ans를 char배열로 변경하여 인덱스별로 저장해주는 식으로 수정하였습니다.
제출결과
  • 16 ms

마무리

  • 그리디한 문제였습니다. 그리디 문제는 그리디라고 생각하는 것 자체가 어려운 것 같습니다.
 BOJ

Related Posts