글 읽기 - 리모콘 문제 관련 질문

minty99 4년 전 0

대충 접근 방식은 코드에 주석으로 적어뒀습니다.

0 ~ 1000000 범위를 전범위 탐색하면 문제는 쉽게 맞힐 수 있지만.. 좀더 효율적으로 해보려고 하는데, 쉽지 않네요. 일단 게시판에 있는 반례들은 다 통과하는 것 같습니다.

제가 놓친 부분이 있을까요? 여러모로 예외적인 케이스가 너무 많은 문제네요 ㅠㅠㅠ...

처음엔 digit 수를 계산하려고 로그도 쓰고 그랬는데 혹시나 실수 오차 때문에 틀리나 싶어서 다 루프로 바꿨는데도 잘 안되는군요.

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tgmath.h>
#include <tuple>
#include <unistd.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> plli;
typedef unsigned char byte;
typedef unsigned int uint;
typedef unsigned long long int ulli;


// val -> k로 갈 때 필요한 버튼 누르기 횟수 (불가능하면 20억)
int test(set<int> &invalid, int val, int k)
{
    // 0 예외처리
    if(val == 0 && invalid.count(0) > 0) return 2e9;
    else if(val == 0) return 1 + abs(k - val);

    int curr = val;
    while(curr > 0) {
        if(invalid.count(curr % 10) > 0) {
            return 2e9;
        }
        curr /= 10;
    }

    int digits = to_string(val).length();
    return digits + abs(k - val);
}

int main()
{
    int k, n;
    scanf("%d %d", &k, &n);

    set<int> s;
    for(int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        s.insert(t);
    }

    // [left, right): k와 자릿수가 같은 수들
    int left = 1;
    while(left < k / 10) left *= 10;
    int right = left * 10;
    if(k == 0) left = 0;
    int ans = 2e9;
    for(int i = left; i < right; i++) {
        ans = min(ans, test(s, i, k));
    }

    ans = min(ans, abs(k - 100));   // 100에서 방향키만 누르는 경우
    ans = min(ans, test(s, 0, k));  // 0이 가능하다면 처리

    // 자릿수가 다른 경우:
    // 자릿수가 하나 적은 경우와 하나 많은 경우를 고려함.
    int valid_M = -1, valid_m = 10;
    for(int i = 1; i < 10; i++) {
        if(s.count(i) == 0) {
            valid_M = max(valid_M, i);
            valid_m = min(valid_m, i);
        }
    }

    // 자릿수가 하나 적은 경우 중 가장 큰 것
    int curr = 0;
    if(valid_M != -1) {
        while(curr * 10 + valid_M < k) curr = curr * 10 + valid_M;
        ans = min(ans, test(s, curr, k));
    }

    // 자릿수가 하나 많은 경우 중 가장 작은 것: 0이 가능하다면 맨 앞 자리 이후로는 0을 채움
    if(valid_m != 10) {
        curr = 0;
        while(curr < k) {
            curr = curr * 10 + valid_m;
            if(s.count(0) == 0) valid_m = 0;
        }
        ans = min(ans, test(s, curr, k));
    }

    printf("%d\n", ans);
}

cozyyg 4년 전 2

k와 자릿수가 같은 수들을 제대로 파악하지 못 하는 문제가 있네요. 반례는 다음과 같습니다.

19 8
0 2 3 4 5 6 7 9

Answer: 3
Output: 12

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

리모콘 문제 관련 질문

minty99 4년 전 0

cozyyg 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말