[BOJ/백준][Gold4] 1082 : 방 번호 (C++)

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

1082번: 방 번호

 

 

[난이도] Gold4
[유형] Greedy

[풀이]
방 번호를 가장 크게 만드려면, 방 번호 숫자의 길이를 가장 길게 만들어야 하며,
그 뒤 가장 큰 자리수의 수들을 큰 수, 즉 N-1과 가까운 수로 만들수록 유리합니다.

이런 수를 만들기 위해 vector<pair<가격,숫자>> p 를 만들고 입력받은 값을 저장해준 뒤
정렬해주어 가격이 싼 것이 앞으로 오도록 합니다.
p[0]가 가장 싼 숫자가 되며, 주어진 돈 M을 이용해  이 숫자를 최대한 많이 사면
숫자를 가장 많이 살 수 있기 때문에 방 번호를 가장 길게 만들 수 있습니다.
이렇게 p[0].second 숫자로만 이루어진 string ret을 만들어 놓고

남은 돈을 이용해 ret[0],ret[1],ret[2]..... 순으로 가능하면 N-1에 가까운 숫자로 바꿔주면
가장 큰 방번호를 만들 수 있습니다.

주의해야 할 것이 p[0].second가 0이라면 전체 숫자가 0이 되지 않도록 가장 앞 숫자를 p[1].second가 되도록
해주어야 합니다.

 

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int N,M,P[10];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&P[i]);
        p.push_back({P[i],i});
    }
    scanf("%d",&M);
    sort(p.begin(),p.end());
    string ret;
    if(N==1){
        puts("0");
        return 0;
    }
    if(p[0].second!=0){
        int cnt = M/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M-=cnt*p[0].first;
    }else{
        int m = M - p[1].first;
        if(m<0) {
            puts("0");
            return 0;
        }
        ret+=to_string(p[1].second);
        int cnt = m/p[0].first;
        for(int i=0;i<cnt;i++) ret+=to_string(p[0].second);
        M=m-cnt*p[0].first;
    }
    for(int i=0;i<ret.size();i++){
        bool ok=0;
        int cur = P[ret[i]-'0'];
        for(int j=N-1;j>=0;j--){
            if(M-(P[j]-cur)>=0){
                M-=P[j]-cur;
                ok=1;
                ret[i]=j+'0';
            }
            if(ok) break;
        }
        if(!ok) break;
    }
    printf("%s",ret.c_str());
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1082.cpp