- 문제
- 리모컨에 눌리지 않는 버튼이 주어졌을 때, 수빈이가 원하는 채널까지 이동하기 위해서 눌러야할 버튼의 최소 횟수 구하기.
- 수빈이가 현재 보고있는 채널은 100번
- 채널은 무한대만큼 있음. ( 정해져있는 범위 없음. )
- 입력 및 출력
[ 입력 ]
- 첫째 줄에 수빈이가 이동하려고 하는 목표 채널 N 입력 ( 0 ≤ N ≤ 500,000 )
- 둘째 줄에 고장난 리모컨 버튼의 개수 M 입력 ( 0 ≤ M ≤ 10 )
- 셋째 줄에 고장난 M 개의 리모컨 버튼 입력
[ 출력 ]
- 채널 N 으로 이동하기 위해 눌러야 할 리모컨 버튼의 최소 횟수 출력.
- 문제 풀이
-
이번 리모컨 문제는 브루트포스 문제이다. 즉, 모든 경우를 하나하나 따져가며 문제를 해결해야한다.
이번 문제 해결의 key point 는 아래와 같다.
- 한번에 갈 수 있는 채널과 한번에 갈 수 없는 채널을 구분.
- 목표 채널을 기준으로 높은 채널에서 접근할지, 낮은 채널에서 접근할지 선택.
- 현재 채널 ( 100번 ) 에서 바로 이동, 숫자 눌러 이동, 숫자 눌러 이동 후 +, - 로 이동 중 가장 작은 횟수 구하기.
-
나는 이번 문제에서 " std::string::npos " 라는 함수를 사용해 해결했다.
- std::string::npos
-> std::string::find 함수를 사용해서 string 안에 어떠한 문자가 존재하는지 확인
-> string 안에 어떠한 문자가 존재하지 않는다면 std::string::npos return
- std::string::npos
-
위의 std::string::npos 함수를 이용해서 직접 접근 가능한 채널을 판별해주었다.
판별하고자 하는 채널의 개수는 목표채널의 2배로 설정해주었고, 반복문을 돌면서 하나씩 true or false 를 판별해 bool type 배열에 저장해주었다. -
그 후 만약 목표 채널이 100이라면 0을 출력해주고 프로그램을 종료시켰고 (return 0 으로 프로그램 종료) 100이 아니라면, 목표채널을 기준으로 큰쪽으로 이동하면서 직접 접근 가능한 채널의 값, 작은 쪽으로 이동하면서 직접 접근 가능한 채널을 각각 구해서 목표 채널 N 에서 얼마나 떨어져있는지를 구했다.
-
이렇게 구한 차이값 2개와 100에서 +, - 로 접근 가능한 횟수 총 3가지 상황을 비교하며 횟수가 가장 작은 값을 출력 후 프로그램을 종료하도록 구현했다.
- 최종 코드
