글 읽기 - 리모컨의 문제점....틀린 이유를 알수 있을까요?

revolution_2 5년 전 0

밑에 분이 제시해주신 30개의 테스트 케이스는 다 맞는데 제출하면 틀리네요 ㅠ

추가적인 테스트를 해봐도 알수가 없네요... ㅠㅠ

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int N, M, Z,size = 0;
int minN = 987654321;
int num[10];
vector<int> remote;

int dfs() {
    if(size - 1 > 0 &&remote.size() == size - 1) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        minN = min(tt, minN);
        if(minN == tt)
            Z = nn;
    }
    if(remote.size() == size) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        minN = min(tt, minN);
        if(minN == tt)
            Z = nn;
    }

    if(remote.size() == size + 1) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        minN = min(tt, minN);
        if(minN == tt)
            Z = nn;
        return 0;
    }

    for(int i = 0; i < 10; i ++) {
        if(num[i] != 1) {
            remote.push_back(i);
            dfs();
            remote.pop_back();
        }

    }
    return 0;
}

int main() {

    cin >> N;
    cin >> M;

    memset(num, 0, sizeof(num));

    int t = N;

    while(1) {
        t /= 10;
        size ++;
        if(t < 1) {
            break;
        }
    }

    for(int i = 0; i < M; i ++) {
        int temp;
        cin >> temp;
        num[temp] = 1;
    }

    if(N == 100) {
        cout << 0;
        return 0;
    }

    dfs();

    int c = Z;
    size = 0;
    while(1) {
        c /= 10;
        size ++;
        if(c < 1) {
            break;
        }
    }

    int ans = minN + size;
    ans = min(ans, abs(N - 100));
    cout << ans;
}

djm03178 5년 전 3

이런 경우까지 걸러낼 수 있다니 데이터는 꽤 강력하군요.

6 9

0 2 3 4 5 6 7 8 9

이 경우 이 코드는 1일 때와 11일 때 각각 검사를 하는데 둘 다 tt가 5가 됩니다. 하지만 11일 때의 검사를 더 늦게 하므로 최종적으로 갱신되는 Z는 11이고, 나중에 size를 계산하면 2가 되므로 답을 7이라고 결론짓습니다. 하지만 실제 정답은 1을 누르고 위로 다섯 채널 올라가는 6입니다.

그리고 한 가지 부탁드리자면 질문을 올릴 때는 코드에 대한 설명을 반드시 넣어주세요. 답변자들은 질문자들에게 새로운 것을 알려주는 데에서 보람을 얻는 것이지, 아무 랜덤 데이터나 넣어보고 반례 찾는 건 재미도 없고 질문자 혼자서도 할 수 있는 일입니다. 코드의 로직을 알아야 그에 대한 잘못된 부분을 찾을 텐데, 아무 설명도 없는 긴 코드를 읽고 싶은 사람은 거의 없을 것입니다.

revolution_2 5년 전 0

답변 감사합니다.

덕분에 해결했습니다.

마지막으로 남겨주신 코드 설명은 다음 질문에서는 꼭 첨부하겠습니다. ^^

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int N, M, Z, size = 0;
int ans = 987654321;
int minN = 987654321;
int num[10];
vector<int> remote;

int dfs() {
    if(size - 1 > 0 && remote.size() == size - 1) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        ans = min(ans, size - 1 + tt);
    }
    if(remote.size() == size) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        ans = min(ans, size + tt);
    }

    if(remote.size() == size + 1) {
        string n = "";
        for(int i = 0; i < remote.size(); i ++) {
            n += remote[i] + '0';
        }
        int nn = stoi(n);
        int tt = N - nn;
        tt = abs(tt);
        ans = min(ans, size + 1 + tt);
        return 0;
    }

    for(int i = 0; i < 10; i ++) {
        if(num[i] != 1) {
            remote.push_back(i);
            dfs();
            remote.pop_back();
        }

    }

    return 0;
}

int main() {

    scanf("%d", &N);
    scanf("%d", &M);

    memset(num, 0, sizeof(num));

    int t = N;

    while(1) {
        t /= 10;
        size ++;
        if(t < 1) {
            break;
        }
    }

    for(int i = 0; i < M; i ++) {
        int temp;
        cin >> temp;
        num[temp] = 1;
    }

    if(N == 100) {
        cout << 0;
        return 0;
    }

    dfs();

    ans = min(ans, abs(N - 100));
    printf("%d", ans);

    return 0;
}

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

문제

문제

출처

ICPC

리모컨의 문제점....틀린 이유를 알수 있을까요?

revolution_2 5년 전 0

djm03178 5년 전 3

djm03178 5년 전 1

revolution_2 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말