[BOJ] 1082번 방 번호 (C++)

1082번: 방 번호 (acmicpc.net)

1082번: 방 번호

 

- 1차 접근

다이나믹 프로그래밍 문제처럼 생겨먹어서 바텀-업으로 점화식을 도출해내기 위해

1차원 배열을 사용하고 보유한 돈(M)을 인덱스로 관리하는 식으로 접근했다.

다음은 도출해낸 점화식이다.

dp[i] = max(dp[i], for max("n" + dp[i-cost[n]])) ('for max'는 숫자 가격 배열 중 가장 큰 가격 배열을 찾는 것을 의미한다.)

여기에 추가적으로, 한자리 수가 아닐 때 앞자리에 0이 들어갈 수 없음을 고려해 제출해본 결과 실패했다.

 

반례는 다음과 같았다. 

input:
5
1 2 2 3 3
20

output:
2000000000000000000

 

해당 테스트 케이스의 정답은 2000000000000000000이다.

하지만 위 점화식에 근거한 dp[20]은 2222222240 이다. 왜냐하면 앞 자리에 0이 들어가는 것을 허용하지 않기 때문이다.

해당 반례를 통해 정석적인 DP의 풀이로는 통과하기 힘들다고 판단했다.

(이 반례 외에도 여러가지 문제가 있었던 접근 방식..)

 

- 2차 접근

그래서 나는 맨 앞자리수를 결정하는 상황이 아니라면

0을 허용하도록 탑-다운 DP와 그리디 개념을 활용하여 접근했다.

구해야하는 값을 시작으로 재귀적으로 최적의 답을 찾아 나갔다.

 

1. 먼저 이미 탐색했던 경우라면 구한 값을 즉시 반환한다.

2. 숫자 가격 배열을 순회하며 현재 가지고 있는 돈으로 만들 수 있는 가장 큰 방번호를 찾는다.

  2-1. 맨 앞 자리 수를 결정하는 상황에서 들어갈 숫자가 0이거나 가지고 있는 돈으로 더 이상 구매할 수 없는 경우는 넘어간다.

3. 찾은 가장 큰 방번호를 리턴한다.

 

수식이 있다면 풍성한 설명을 할 수 있지만 강의 목적이 아닌 기록 목적이니.. 생략하겠다.

여튼 해당 방식으로 개선 후에 통과를 받을 수 있었다.

 

- 특이 사항

가장 큰 방번호를 찾을 때 단순하게 문자열 비교하는 방식 (부등호, compare() 함수 등)으로는 판단할 수 없었다.

길이가 긴 문자열이 더 크다고 판단하지 않기 때문이다. 그래서 방번호를 비교하는 함수를 따로 만들었다.

이 외에도 사소한 처리들이 많이 요구되서 골치아팠다..;

- 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 50
using namespace std;

int N, M;
vector<int> list;
string dp[MAX+1];
bool visits[MAX+1];

bool compareRoom(string room1, string room2) {
    if(room1.length() < room2.length()) return true;
    else if (room1.length() > room2.length()) return false;
    else return room1 < room2;
}

string findMaxRoom(int m, bool isHead) {
    if(dp[m] != "" && visits[m]) return dp[m];
    
    string maxRoom = "", curRoom;

    for(int i = 0; i < list.size(); i++) {
        if(isHead && i == 0) continue;
        if(m - list[i] < 0) continue;

        curRoom = to_string(i) + findMaxRoom(m - list[i], false);

        if(compareRoom(maxRoom, curRoom))
            maxRoom = curRoom;      
    }

    dp[m] = maxRoom;
    visits[m] = true;

    return maxRoom;
}

int main() {
    int n, maxRoom;
    string nextRoom, answer;

    for(int i = 0; i <= M; i++)
        dp[i] = "";

    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> n;
        list.push_back(n);
        dp[n] = to_string(i);
    }
    cin >> M;

    findMaxRoom(M, true);

    answer = dp[M] == "" ? "0" : dp[M];
    cout << answer << '\n';

    return 0;
}

 

 

운이 좋게 몇 번 안틀렸다!