백준 1107번 C++ 리모컨 문제 (추가)

현재 상황...

반례를 고쳤더니 시간 초과가 떴다

그래도 그냥 정리하기 위해 포스팅

나중에 맞으면 다시 고쳐서 올림

(추가)

어제 추가된 틀렸습니다와 시간 초과 ㅋㅋㅋㅋ

아마 둘 다 그냥 틀렸습니다겠지 ㅎㅎ

저거 원래 있던 코드로 하다가 뻘짓해서 난 결과이다

리모컨은 왜 부수고 난리냐?

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

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

코드(현재 시간초과)

//
// Created by az91t on 2019-05-17.
//
 
#include <iostream>
using namespace std;
 
int isBroken(int n, int number[]){
    if(n==0) {
        return 1;
    }
 
    int digit;
    while(n!=0) {
        digit=n%10;
        if(number[digit]==-1) {
            return 1;
        }
        n/=10;
    }
    return 0;
}
 
int numberOfDigit(int n) {
    int digit=0;
    if(n==0) {
        return 1;
    }
    while(n!=0) {
        digit++;
        n/=10;
    }
    return digit;
}
 
int main() {
    int N, M, channel=100;
    cin>>N>>M;
 
    int number[10];
    for(int i=0; i<=9; i++) {
        number[i]=i;
    }
 
    if(M>0) {//고장난 버튼이 있는 경우
        int broken;
        for(int i=0; i<M; i++) {
            cin>>broken;
            number[broken]=-1;
        }//-1이면 고장난 버튼
    }
 
    if((N>97&&N<103)||M==10) {
        cout<<abs(N-channel)<<"\n";
        return 0;
    }
 
    int goal1=N, goal2=N;
    while(isBroken(goal1, number)!=0
    &&isBroken(goal2, number)!=0) {
        goal1++;
        if(goal2>0) {
            goal2--;
        }
    }
 
    int min=goal1;
    if(isBroken(goal2,number)==0) {
        min=goal2;
    }
 
    int count;
    if(min==100) {
        count=abs(N-min);
    } else {
        count=numberOfDigit(min)+abs(N-min);
    }
 
    cout<<count<<"\n";
 
    return 0;
}

코드(갈아엎은 후)

//
// Created by az91t on 2019-05-18.
//
 
#include <iostream>
using namespace std;
int M, brokenList[10]={0,};//고장난 버튼 리스트
 
bool isBroken(int n) {
    for(int i=0; i<M; i++) {
        if(n==brokenList[i]) {
            return true;
        }
    }
    return false;
}
 
bool isPossibleChannel(int n) {
    if(n==0) {
        if(isBroken(n)){
            return false;
        } else {
            return true;
        }
    }
 
    while(n!=0) {
        if(isBroken(n%10)) {
            return false;
        }
        n/=10;
    }
    return true;
}
 
int numberOfDigit(int n) {
    int digit=0;
    if(n==0) {
        return 1;
    }
    while(n!=0) {
        digit++;
        n/=10;
    }
    return digit;
}
 
int main() {
    int N, channel=100;
    cin>>N>>M;
 
    if(M>0) {
        for(int i=0; i<M; i++) {
            cin>>brokenList[i];
        }
    }
 
    if((N>97&&N<103)||M==10) {
        cout<<abs(N-channel)<<"\n";
        return 0;
    }
 
    int nPlus=N, nMinus=N;
    while(!isPossibleChannel(nPlus)
          &&!isPossibleChannel(nMinus)) {
        nPlus++;
        if(nMinus>0) {
            nMinus--;
        }
    }
 
    int possibleChannel=nPlus;
    if(isPossibleChannel(nMinus)) {
        possibleChannel=nMinus;
    }
 
    int min=numberOfDigit(possibleChannel)+abs(N-possibleChannel);
    if(min>abs(N-channel)) {
        min=abs(N-channel);
    }
 
    cout<<min<<"\n";
    return 0;
}

왜 틀렸었나(맞기 전)

0에 대한 예외 처리를 해주지 않았기 때문이다

질문게시판을 뒤진 결과

0

3

1 2 3

을 포함, 예외처리가 필요했다

포스팅을 쓰는 와중에 다시 보니 틀려서 다시 고침

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

int isBroken(int n, int number[]){
    if(n==0) {
        return 1;
    }

이 부분을

int isBroken(int n, int number[]){
    if(number[0]==-1&&n==0) {
        return 1;
    }

이렇게 고쳤는데... 이것도 틀린 걸까...

아무튼 다시 해결해보자

왠지 이렇게 하면 시간초과 날 것 같은데 ㅎㅎ... 하면서 했는데

왜 슬픈 예감은 틀린 적이 없나...

그렇다고 다른 사람 풀이 보긴 싫고 참 무슨 마음인지 모르겠다

왜 틀렸었나(맞은 후)

핵심이 되는 브루트 포스인지 뭔지 그 부분은 안 틀렸던 것 같다...

아마 앞뒤로 틀렸었던 것 같다

이번에는 진짜... 내가 이렇게 머리가 나쁜가 자책했다

사실 알고리즘 계속 해봐야 아는 거고, 내가 일부러 정답률 낮은 거 도전해가면서 스스로 스트레스 받고 있다는 거 인정한다

그런데도 오늘 동아리 가서도 어떻게 하면 맞을 수 있을지 생각했다

오늘 하루는 쉬자고 생각했는데... 결국 12시 넘어서 씻고 노트북 앞에 앉았다.

고치는 데는 얼마 안 걸렸다. 그냥, 질문 게시판을 뒤져서 반례를 다 넣어 보았다.

첫 줄부터 왜 이렇게 코드를 썼나 생각해보자

#include <iostream>
using namespace std;
int M, brokenList[10]={0,};//고장난 버튼 리스트
 

데이터 영역에 고장난 버튼 개수와 고장난 버튼 리스트 변수를 선언해준다

이유는 밑에 나올 isBroken함수와 isPossibleChannel함수의 변수를 최소화해주기 위함

bool isBroken(int n) {
    for(int i=0; i<M; i++) {
        if(n==brokenList[i]) {
            return true;
        }
    }
    return false;
}

isBroken 함수는 해당 숫자가 고장난 버튼을 포함하고 있으면 true를 반환한다

따라서 하나라도 찾으면 반복문을 탈출해서 true 리턴

고장 안 났으면 for문을 다 돌고 빠져나와서 false 리턴

bool isPossibleChannel(int n) {
    if(n==0) {
        if(isBroken(n)){
            return false;
        } else {
            return true;
        }
    }
 
    while(n!=0) {
        if(isBroken(n%10)) {
            return false;
        }
        n/=10;
    }
    return true;
}

가장 중요한 isPossibleChannel 함수이다

기존 코드에서 0을 안 걸러줘서 배렸기 때문에 n==0일 때 추가

else는 그다지 쓰고 싶지 않았는데 써버렸다

n이 0일 때 간과할 수 있는 게, 0이 고장난 숫자일 때와 아닐 때를 나눠줘야 한다는 점이다

만약 0이 아니라면 while문을 도는데 n의 자릿수 하나하나를 검색해서 하나라도 고장난 숫자가 걸리면

반복문을 탈출해서 false를 리턴한다

만약 고장난 숫자가 하나라도 없다면 반복문을 빠져나와서 true 리턴

int numberOfDigit(int n) {
    int digit=0;
    if(n==0) {
        return 1;
    }
    while(n!=0) {
        digit++;
        n/=10;
    }
    return digit;
}

자릿수를 반환해주는 numberOfDigit 함수

마지막 main 함수

if(M>0) {
        for(int i=0; i<M; i++) {
            cin>>brokenList[i];
        }
    }

i번째 인덱스에 고장난 숫자 입력받아서 넣어준다

if((N>97&&N<103)||M==10) {
        cout<<abs(N-channel)<<"\n";
        return 0;
    }

N이 98,99,100,101,102일 때는 +나 -로 조작해서 채널을 이동하는 게 최소로 누르기 때문에

N-channel의 절댓값을 출력하고 return 0

M==10이라는 건 모든 숫자가 고장났다는 뜻이므로 +나 -만 이용해야한다

따라서 최솟값은 N-channel의 절댓값이 된다

 int nPlus=N, nMinus=N;
    while(!isPossibleChannel(nPlus)
          &&!isPossibleChannel(nMinus)) {
        nPlus++;
        if(nMinus>0) {
            nMinus--;
        }
    }

만약 그런 경우가 아니라면?

N에서 출발해서 반복문을 따라 +1, -1 당하는(?) 변수 nPlus, nMinus를 선언한다

이 루프문의 조건은 어느 하나라도 누르기 가능한 채널이 된다면 반복문을 탈출하는 것이다

난 이게 효율적이라고 생각했는데 ㅎ 아니었던가보다 ㅎㅎ... 아무튼

nMinus가 0보다 클 때 즉 최소 1일 때까지만 -1하므로 nMinus는 아무리 작아도 0이 된다

int possibleChannel=nPlus;
    if(isPossibleChannel(nMinus)) {
        possibleChannel=nMinus;
    }

일단 가능한 채널은 nPlus라고 생각하자

하지만 만약 실제로는 고장나지 않은 채널의 번호가 nMinus라면?

가능한 채널은 nMinus가 된다.

둘 다 고장나지 않은 채널이어도 nMinus가 가능한 채널이 된다

int min=numberOfDigit(possibleChannel)+abs(N-possibleChannel);
    if(min>abs(N-channel)) {
        min=abs(N-channel);
    }

마지막으로 하나 더 처리를 해주어야 한다.

0도 한자리 수이다. 따라서 처리를 해주려고 했는데 그 이유를 까먹었다...

아무튼 min을 출력하면 끝!

수고했다 이틀 동안의 나야...

왜 백준 시뮬레이션 탭에 들어가서 이 고생을 한 거지?

이번에도 깨달은 것

'틀렸습니다'는 말그대로 내 코드가 틀렸기 때문에 뜨는 것이었다...

그리고 솔직히, 너무 답답해서 검색해서 다른 사람들의 코드를 보고 다녔다.

그런데 솔직히 알아먹기 힘들었다 내 머리가 딸려서 그런 건지 ㅎㅎ...

그러다가 어떤 분 코드 보고 로직이 나랑 비슷한데, 왜 나는 틀린 거지 하고 찬찬히 보았더니

위에 말했던 n==0일 때를 처리해주지 않아서였다...

그럼에도 왜 다른 분들이 0부터 1000002인지 1000001까지 왜 쭉 도는지 잘 이해를 못해서

그냥 나는 내 방법대로 하기로 했다

맞았으니 된 거지...가 아니라 다른 사람들이 다들 그렇게 푸는 데에는 이유가 있는 거겠지?

이제 마음의 여유가 좀 생긴 것 같다

조급해하지 말자!