BOJ1020 디지털카운터(C++)

---

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

풀이방법 : dp, 역추적, 구현

---

---

사고 과정

DP 임을 알고 시작한 문제다

수를 하나씩 늘리면 당연히 안되니까 시간을 줄여야하는데

자릿수를 잘 사용하면 될 것 같다고 생각했다.

일단 cnt배열 int cnt[i] = (한자리수 i의 선분 갯수) 을 만들어놓는다.

가장 선분이 많이쓰이는 8이 7개, 최대 15칸이므로

dp테이블을 다음과같이 잡았다. dp[16][106]

bool dp[i][j] = (뒤에서부터 i번째 자리에서 선분 j개로 완성 가능한 수가 있는지 여부)

여기까지는 구현이 쉬웠는데, 그 다음이 문제였다.

---

이제 다음에 올 숫자를 찾을 차례다.

1234를 예로 들면, 일단 1234를 만드는데는 2+5+5+4=16개의 선분이 필요하다.

일의 자리부터 하나씩 올려본다. 1235, 1236, ...1239.

일단 일의 자리는 4보다 큰 수들 중 4개가 필요한 수를 찾을것이다. 5,6,7,8,9 중엔 없다.

여기서부터 또 1씩 더하면 시간초과 날거니까, 이제 십의 자리를 하나씩 늘리는 것이다.

12xx까진 고정이다. xx에 필요한 선분 수는 16 - 7 = 9개.

십의 자리를 4부터 늘려가며, dp[1][9 - cnt[4]]가 true인지 확인한다.

이는 십의 자리에 4가 고정이라고 치면 일의 자리에 5개의 선분을 채울 수 있는지 확인하는 것이다.

9 - cnt[4] = 5이고, dp[1][4]는 true이다.

십의 자리를 4로 고정하고, 나머지 자리를 따로 카운팅 하면된다.

만약 백의 자리를 고정했고 dp[2][?]를 찾았다면 십의 자리부터 카운팅 하면 된다.

1234와 별개의 예시로 어떤 수가 123xx 까지 확정되었다고 치고, 남은 채워야할 선분 수가 k라면

십의 자리부터 0~9까지 돌면서 dp[1][k - cnt[i]]가 true라면 십의자리 고정하고 일의자리로 넘어가면 된다..

정답 출력은 만약 다음 숫자가 현재 수보다 크다면 (큰 수 - 작은 수),

그렇지 않다면 (현재 자릿수 최댓값 - 큰 수) + 작은 수 해주면 된다.

---

#include <iostream>

using namespace std;

int n;
int cnt[11] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 5 };
string s;

int sum;
bool dp[16][106];
string ans;
long long ansL;

void printDiff() {
    bool isBigger = (ans > s);

    long long mul = 1;
    long long from = 0;
    long long to = 0;
    for (int i = 0; i < n; ++i) {
        to += mul * (ans[n - i - 1] - '0');
        from += mul * (s[n - i - 1] - '0');
        mul *= 10;
    }

    if (isBigger) {
        cout << to - from;
    }
    else {
        cout << (mul - from) + to;
    }
}

void solve() {

    for(int i = 0; i < 10; ++i) {
        dp[1][cnt[i]] = 1;
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < 106; ++j) {
            for (int k = 0; k < 10; ++k) {
                if (j - cnt[k] >= 0 && dp[i - 1][j - cnt[k]]) {
                    dp[i][j] = 1;
                }
            }
        }
    }

    ans = s;

    int fill = 0;

    int idx = 0;

    bool flag = false;
    for (int i = 1; i <= n; ++i) {
        int p = s[n - i] - '0';
        int now = p;

        fill += cnt[p];
        while (now < 9) {
            ++now;
            if (i == 1) {
                if (fill == cnt[now]) {
                    ans[n - i] = now + '0';
                    idx = n - i + 1;
                    fill -= cnt[now];
                    flag = true;
                    break;
                }
            }
            else {
                if (fill >= cnt[now] && dp[i - 1][fill - cnt[now]]) {
                    ans[n - i] = now + '0';
                    idx = n - i + 1;
                    fill -= cnt[now];
                    flag = true;
                    break;
                }
            }
        }
        if (flag) {
            break;
        }
    }

    for (int i = idx; i < n; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (i == n - 1) {
                if (cnt[j] == fill) {
                    ans[i] = j + '0';
                    fill -= cnt[j];
                    break;
                }
            }
            else {
                if (fill >= cnt[j] && dp[n - i - 1][fill - cnt[j]]) {
                    ans[i] = j + '0';
                    fill -= cnt[j];
                    break;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;
    n = s.length();
    for (int i = 0; i < n; ++i) {
        sum += cnt[s[i] - '0'];
    }
    solve();
    printDiff();
}

---

후기

ㅋㅋ
ㅋㅋㅋㅋㅋㅋㅋ
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

푸는 맛은 있었다..

DP란 뭘까