1107번: 리모컨

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

1107번: 리모컨

채널 N으로 이동하는 데에는 두 가지 방법이 있다. 이전/다음 채널 버튼만 이용하는 경우와, 숫자 버튼으로 채널을 이동한 다음 이전/다음 채널로 이동하는 경우.

숫자 버튼으로 채널을 이동하는 경우는 비용을 최소로 할 가능성이 있는 채널을 고르는 것이 중요한데, 이를 위해선 우선 숫자 버튼을 눌러 채널을 이동했다고 가정해야 한다.

숫자를 눌러 이동한 채널 K에 대해, 채널 K에서 채널 N으로 이동하는 비용은 채널 K로 이동할 때의 비용 t에 대해 |N - K| + t가 된다.

또한, 채널 K의 채널값이 채널 N보다 크거나 같을 경우, 이 이상 숫자 버튼을 눌러 채널 K의 채널값을 늘린다 한들 비용을 더 늘릴 뿐이므로 이 이상 숫자 버튼을 누를 필요가 없다.

#include <cstdio>

#define MAX_CHN 500000

int abs(int a) { return a >= 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }

// broken[i]: 버튼 i가 고장났다면 true
bool broken[10];
// N: 타겟 채널, ans: 채널 N으로 이동하는 최소 비용
int N, ans = MAX_CHN;

// 0번 채널로 이동한 것이 아닐 경우
// 버튼을 t번 눌러 현재 채널 K로 이동했을 때 최소 비용을 계산
void brute_force(int K, int t) {
    // 현재 채널에서 채널 N으로의 비용을 기존 최소 비용과 비교
    ans = min(abs(N - K) + t, ans);
    // 현재 채널이 목표 채널보다 크거나 같을 경우 더 버튼을 누를 필요 없다
    if (K >= N) return;
    // 현재 채널에서 숫자 버튼을 추가로 눌러
    // 다른 채널로 이동했을 때의 최소 비용을 기존 최소 비용과 비교
    for (int i = 0; i < 10; i++) if (!broken[i]) brute_force(K * 10 + i, t + 1);
}

int main() {
    // M: 고장난 버튼의 수, buf: 고장난 버튼을 입력받을 버튼
    int M, buf;
    // 문제 조건을 입력받는다
    scanf("%d %d", &N, &M);
    while (M--) {
        // 누를 수 없는 버튼을 broke에서 제거
        scanf("%d", &buf);
        broken[buf] = true;
    }

    // 0번 채널은 재귀로 돌리지 않고 따로 계산
    if (!broken[0]) ans = min(ans, N + 1);
    // 1번 채널부터 가능한 모든 채널에 대해 최소 비용을 계산
    for (int i = 1; i < 10; i++) if (!broken[i]) brute_force(i, 1);
    // 현재 채널에서 이전/다음 채널 버튼만 눌렀을 때의 최소 비용과
    // 브루트포스로 계산한 최소 비용을 비교해 더 작은 값을 출력
    printf("%d\n", min(ans, abs(N - 100)));

    return 0;
}

따라서 채널 K로 숫자 버튼만을 이용해 이동했을 경우, 채널 K의 채널값이 채널 N보다 작다면 추가적으로 숫자 버튼을 눌러 채널을 이동하는 경우를 고려할 수 있다.