백준 1105번: 팔

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

1105번: 팔

dfs를 이용해 가능한 경우를 모두 탐색할 수도 있고, 그리디 알고리즘을 이용해 답을 구할 수도 있다.

• dfs

어느 수에서 8을 없애는 가장 좋은 방법은 해당 수를 직전 수인 7 혹은 직후 수인 9로 만드는 것이다. 0부터 6까지로 만드는 경우는, 8을 7로 만드는 경우가 가능할 때 굳이 셀 필요가 없기 때문이다. 따라서 각 수를 노드로, 각 수에 존재하는 8을 7 혹은 9로 바꾸어 얻을 수 있는 모든 수와의 관계를 에지라고 할 때, 이 문제는 dfs를 이용하여 가능한 경우를 최소로 하여 탐색할 수 있다.

#include <cstdio>
#include <map>

using namespace std;

#define MAX_DGT 10
#define MAX_R 200

// L, R: 가능한 수의 범위, arr[i]: 10 ^ i
int L, R, arr[MAX_DGT] = { 1, };
// visit[i]: 노드 i를 방문했다면 i에서 8의 개수, 아니라면 존재하지 않음
map<int, char> visit;

int min(int a, int b) { return a < b ? a : b; }

// node의 비용을 계산한 뒤 dfs 실행
int dfs(int node) {
    // 비용을 계산한 후 dfs한 값을 저장할 공간
    int ret = MAX_DGT;
    // 범위를 벗어난다면 MAX_DGT 반환
    if (node < L || node > R) return MAX_DGT;
    // 아직 node를 방문한 적 없다면
    if (visit.find(node) == visit.end()) {
        // node에서 8의 개수를 센 뒤
        for (int i = 0; i < MAX_DGT && arr[i] <= node; i++)
            if ((node / arr[i]) % 10 == 8) visit[node]++;

        // 각 8의 위치를 7 혹은 9로 바꿔서 탐색한 결과 중
        // 최솟값을 ret에 저장
        for (int i = 0; i < MAX_DGT && arr[i] <= node; i++)
            if ((node / arr[i]) % 10 == 8)
                ret = min(ret, min(dfs(node + arr[i]), dfs(node - arr[i])));

        // 현재 노드에서 8의 개수와 dfs한 결과 중 최솟값을 반환
        return min(visit[node], ret);
    }

    // node가 이미 visit에 존재한다면 그냥 현재 노드에서 8의 개수만 반환
    return visit[node];
}

int main() {
    // 8의 개수를 최소화할 범위를 입력받은 뒤
    scanf("%d %d", &L, &R);
    // 10 ^ n꼴을 모두 완성시키고
    for (int i = 1; i < MAX_DGT; i++) arr[i] = arr[i - 1] * 10;

    // L과 R에서 인접한 수를 모두 탐색
    printf("%d\n", min(dfs(L), dfs(R)));

    return 0;
}

• 그리디

L과 R의 각 n( = 10 ^ k)의 자리를 비교해 보자. 만일 L의 n의 자리와 R의 n의 자리가 둘 다 8이 아니라면, R의 n의 자리 수 R_n에 대해 R_n * (10 ^ k)는 L과 R 사이이며 8의 개수가 0개임이 자명하다. 하지만 그렇지 않다면, 기존에 만든 8의 개수를 최소화하는 수가 여전히 범위 [L, R] 안에 있으려면 구한 수의 맨 왼쪽에 8을 더해야만 한다. 이 과정을 반복한다면 8의 개수를 최소화하는 수를 구할 수 있으므로, 이 수 안의 8의 개수를 출력하면 정답을 얻을 수 있다.

#include <cstdio>

int main() {
    // L, R: 가능한 수의 범위, ans: 가능한 8의 최소 개수
    int L, R, ans = 0;

    // 문제의 조건을 입력받은 뒤
    scanf("%d %d", &L, &R);
    // L과 R의 각 자리에 대해
    while (R) {
        // L의 현재 자리와 R의 현재 자리가 같다면
        // 8의 개수를 최소화하는 어떤 수의 왼쪽에 8을 추가
        // 그렇지 않다면 8의 개수를 최소화하는 수는
        // (R의 현재 자리 수) * 10 ^ (현재 자리수의 순서)가 된다
        ans = (L % 10 != R % 10) ? 0 : ans + (L % 10 == 8);
        // L과 R의 다음 자리 수에 대해 비교
        L /= 10;
        R /= 10;
    }

    // L과 R 사이의 수 중 8이 가장 적은 수의 8의 개수를 출력
    printf("%d\n", ans);

    return 0;
}