[C++] 백준 1107번 리모컨

브루트 포스 완전탐색 문제.

이 문제는 두 번 풀게됐는데,

처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서

백준 게시판을 참고해서 다시 풀게됐다.

정답 비율이 낮지만 반례를 보면서 디버깅을 하다보면 풀 수 있었던 문제다.

 

글 읽기 - [반례모음]

반례는 위 사이트를 참고했다.

 

문제풀이

TV를 보는데 현재 채널이 100이다. 그리고 채널을 돌리려고 하는데, 일부 숫자가 고장이 났다.

+버튼은 +1채널, -버튼은 -1채널인데 0채널에서는 변화하지 않는다.

 

조건은 간단하다. 위 조건만 고려해주면된다.

 

처음에 푼 방식은 조건을 나누어서 계산해서 풀었다.

1. 모두 +로 계산했을 때,
2. 모두 -로 계산했을 때,
3. 숫자로 최대한 가까운 곳을 찾고, +버튼이나 -버튼으로 찾아가게 하기.

1번이나 2번은 반복문을 통해서 구현했었고(그냥 빼기만 해줬어도 됐다.)

3번은 재귀함수를 통해서 수열을 구하는 식으로 최대한 근접한 수를 찾았다.

그런데 3번같은 경우, 범위가 넓어서 그런지 시간이 엄청나게 많이 걸렸다. 물론 정답은 됐었다.

/* */ #include <iostream> #include <cstring> #include <string> #include <math.h> #include <algorithm> using namespace std; string wantChannel; int wantChannelNum; int numByBtn = 100; int breakBtnNum; int input; int currentChannel = 100; int result; bool btnCheck[10]; void findNum(int idx, string curNum, int goalChannel) {     if (idx > 6) {         return;     }     else {         if (curNum != "") {             int diffCurNum = abs(goalChannel - stoi(curNum));             int diffOriginal = abs(goalChannel - numByBtn);             if (diffCurNum < diffOriginal || ( (diffCurNum == diffOriginal) && curNum.length() < to_string(numByBtn).length() ) ) {                 numByBtn = stoi(curNum);             }         }         for (int i = 0; i < 10; i++) {             if (btnCheck[i]) {                 if (curNum == "") { curNum = "0"; }                 int temp = (stoi(curNum) * 10 + i);                 findNum(idx + 1, to_string(temp), wantChannelNum);             }         }     } } int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);     memset(btnCheck, 1, sizeof(btnCheck));     cin >> wantChannel;     cin >> breakBtnNum;     for (int i = 0; i < breakBtnNum; i++) {         cin >> input;         btnCheck[input] = false;     }     wantChannelNum = stoi(wantChannel);     int addOrSum = 0;     while (currentChannel != wantChannelNum) {         if (currentChannel < wantChannelNum) {             currentChannel++;             addOrSum++;         }         else {             currentChannel--;             addOrSum++;         }     }     findNum(0, "", wantChannelNum);     int result1 = addOrSum;     int result2 = abs(numByBtn - wantChannelNum) + to_string(numByBtn).length();     result = min(result1, result2);     cout << result;     return 0; }

위 코드가 처음에 푼 코드이다.

이 코드를 왜 캡쳐를 해서 설명하지 않냐면 그리 좋은 코드는 아니라고 생각하기 때문이다.

1. 너무 지저분하고, 예외처리된 부분이 스파게티처럼 꼬여있다.
2. 재귀를 하지 않고도 이 문제를 풀 수 있다. 즉, 시간을 훨씬 단축시킬 수 있다.

그래서 이 코드는 정답 코드이긴 하지만, 다른 코드로 문제를 설명해 보겠다.

 

 

두번째로 푼 방식을 설명해보겠다. 문제의 기본설명은 같으므로 생략하고,

• 입력받는 채널은 0 ~ 500,000 까지이다 -> 따라서 나는 채널의 경우의 수를 1,000,000까지만 고려해주면 된다.

게시판을 찾다가 알게된 풀이인데, 위 코드처럼 굳이 재귀로 가능한 수를 찾지 않고, 0 ~ 1,000,000까지 가능한 수를 찾고 버튼을 최소로 누를 수 있다면 값을 갱신해주면 된다.

그리고 왜 1,000,000까지냐면 만일 원하는 채널이 500,000인데, 숫자 6개의 버튼 0, 1, 2, 3, 4, 5가 고장이 났다면 정답은 777,777 채널에서 -버튼으로 내려오는 식으로 구현해줘야 한다. 숫자 8개 버튼 0 ~ 7까지 고장이 났다면 888,888 채널에서 내려와야 한다.

 

바로 코드로 확인해보자.

사용한 STL과 변수와 메서드

문자열을 정수형으로 변환해주는 stoi(int _Val) 메서드를 사용하기 위해 string STL을 사용했다.

숫자를 절대값으로 취해주는 abs(int _Val) 메서드를 사용하기 위해 math.h STL을 사용했다.

• wantChannel : 옮기길 원하는 채널을 저장하는 문자열 변수.
• breakBtnCnt : 고장난 버튼의 개수를 저장하는 변수.
• input : 입력용 변수.
• btnBreak 배열 : 0 ~ 9 중 무슨 숫자가 고장났는지 저장하는 변수. true가 고장났다는 뜻이 된다.
• result : 결과값. 최소의 버튼을 누른 것을 저장하게 된다.

checkAvailable(int num) 메서드는 0 ~ 1,000,000까지 돌아보면서, 가능한 숫자들에 대해 최소로 누르는 버튼의 횟수를 갱신해주는 메서드이다.

 

메인함수

처음에 원하는 채널을 입력받고, 고장난 버튼의 개수와 어떤 버튼인지를 입력받는다.

그리고 result, 최소로 누르는 버튼의 횟수를 저장하는 변수에 초기값으로

최초채널인 100에서 원하는 채널을 뺀 절대값으로 초기화 해준다.

이는 +, -버튼으로만 움직였을 때의 횟수로 초기화를 해주는 것이다.

 

그리고 0~ 1,000,000까지 가능한 숫자를 확인하는 메서드 checkAvailable(int num)를 호출하면서

result를 갱신해나간다.

 

checkAvailable() 메서드

매개변수로 넘어온 채널값을 정수형을 문자열로 변환해주는 to_string()메서드로 문자열로 변환해준다.

이는 각 자리수가 숫자버튼으로 가능한 숫자인지 편하게 확인하기 위함이다.

canUse 변수가 true라면 모든 자리의 숫자가 숫자버튼으로 가능하다는 뜻이다.

 

반복문으로 각 자리의 숫자가 고장이 났는지 확인하고, 고장이 나있다면 canUse 변수를 false로 바꾸고 반복문을 탈출한다.

만일 canUse가 true가 아니라면 함수를 그대로 종료하고,

canUse가 true라면 임시값 res에 |현재 채널값 - 가려는 채널값| + 현재 채널값의 길이

를 저장해 준다. 현재 채널값 - 가려는 채널값은 +, -버튼을 얼마나 눌러야 하는지를 의미하고 현재 채널값의 길이는 해당 채널을 갈 때 누르는 버튼 횟수를 의미한다.

 

처음에 맞췄을 때, 시간이 너무 오래걸려서 잘못 풀었다고 생각해서 게시판을 뒤졌다.

제대로된 풀이를 찾고나서야 이 문제를 어떻게 풀어야 하는지 알게됐다.

시간복잡도는 항상 중요하게 생각해야 한다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.