[Algorithm] Baekjoon 1082번 : 방 번호

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
struct Node
{
    int num;
    int cost;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.cost == b.cost)
    {
        return a.num > b.num;
    }
    return a.cost < b.cost;
}
 
int n, m;
int maxDigitCount = 0;
int costs[10] = { 0 };
string answer = "";
 
void DFS(int num, int money)
{
    if (answer.size() == maxDigitCount)
    {
        cout << answer;
        exit(0);
    }
 
    for (int i = num; i >= 0; --i)
    {
        if (money >= costs[i])
        {
            answer.push_back(i + '0');
            DFS(i, money - costs[i]);
            answer.pop_back();
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    if (n == 1)
    {
        cout << 0;
        return 0;
    }
 
    vector<Node> nodes;
    for (int i = 0; i < n; ++i)
    {
        cin >> costs[i];
        nodes.push_back({ i,costs[i] });
    }
 
    cin >> m;
 
    int curMoney = m;
    sort(nodes.begin(), nodes.end(), cmp);
 
    if (nodes[0].num == 0)
    {
        ++maxDigitCount;
        curMoney -= nodes[1].cost;
        
        if (curMoney < 0)
        {
            cout << 0;
            return 0;
        }
    }
 
    maxDigitCount += curMoney / nodes[0].cost;
 
    for (int i = n - 1; i >= 1; --i)
    {
        if (m >= costs[i])
        {
            answer.push_back(i + '0');
            DFS(i, m - costs[i]);
            answer.pop_back();
        }
    }
}
 
 
 

 

먼저 dp를 이용한게 아닌, 다른 방식으로 풀어봤다.

 

최대값을 구하는게 문제이니, 일단 무조건 자리수가 많은게 이득이다.

그렇기 때문에 주어진 정보들로 만들 수 있는 최대자리수(maxDigitCount)를 먼저 구한다.

어떤 숫자든 상관없이, 그냥 만들 수 있는 최대자리수를 구한다.

 

최대자리수를 구하는 방법으로는 먼저 각 가격순으로 오름차순정렬을 한다. 

정렬 후, 해당 컨테이너의 0번째 원소의 숫자가 0일경우 현재 돈에서 숫자0의 가격을 빼는게 아니라 1번째 원소의 숫자의 가격을 뺀다.

왜냐면 숫자를 0부터 만들 수 없기 때문이다.(0을 출력할거 아니면)

그렇기 때문에 그다음으로 싼 1번째 숫자를 맨 앞에 세운다는 의미이다.

숫자 한개를 세웠으니 ++maxDigitCount를 해준다.

그다음은 그냥 남은 돈 / 1번째원소 숫자의가격을 maxDigtCount에 누적시킨다.

최대자리수를 만드는게 목적이니, 숫자상관없이 제일 싼걸로 자리수만 채우는것이다.

 

여기까지했으면 일단 기준이 되는 최대자리수를 구했다. 우리가 출력해야할 정답의 자리수는 무조건 이 최대자리수에 해당한다. 

 

이후에는 그냥 제일 큰수부터 붙였다가 뗐다가를 하면서 최대자리수를 만족하는 순간 해당값을 출력하고 종료했다.

코드를 제출했을 시, 통과는 했지만 시간이 매우 오래걸렸다.

애초에 dp태그에 있는 문제라서 dp를 활용해야하는게 의도된 문제이지만, input값이 작아서 위 경우를 시도해봤는데 통과는 한다.

일단 극한의 효율을 떠나서, 자기가 어떤 아이디어를 떠올렸을 때 그것을 검증하기위해 코드를 작성하고 제출하는것이 중요하다고 생각한다. 이 아이디어가 나중에 어떻게 도움될지 모르기 때문이다.

 

어쨌든, 위 코드는 시간효율이 너무 안좋으니 다른풀이를 생각해본다.

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
int costs[10] = { 0 };
string dp[51] = { "" };
 
bool compareStringNum(const string& a, const string& b)
{
    if (a.size() < b.size()) return true;
    else if (a.size() > b.size()) return false;
    else return a < b;
}
 
string DFS(int cost, bool isFirst)
{
    string& result = dp[cost];
    if (result != "") return result;
 
    for (int i = 0; i < n; ++i)
    {
        if (isFirst && i == 0) continue;
        if (cost < costs[i]) continue;
 
        string temp = to_string(i) + DFS(cost - costs[i], false);
 
        if (compareStringNum(result, temp))
        {
            result = temp;
        }
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> costs[i];
    }
 
    cin >> m;
 
    DFS(m, true);
    
    if (dp[m] == "") cout << 0;
    else cout << dp[m];
}
 
 
 

 

 

이걸 왜 처음부터 생각못했는지 자책하게되는 코드다.

간단하게 그냥 dp[금액] = 최대문자열숫자   으로 Top-Down하는 코드이다.

문자열의 맨앞에는 0이오면 안되니까, DFS함수 매개변수에 맨앞인지 아닌지를 구별해주는 bool변수 하나를 추가로 넣어준다.

이외는 그냥 가격이 허용되는 한, 숫자들을 전부 붙여주면서 dp테이블을 업데이트해주면 된다.