[백준 / C언어] Day48. 리모컨 (1107)

2024. 07. 21 - 코딩테스트 스터디 Day48

 
 

01. 문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
 

02. 입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장 난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

 
 

03. 출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
 
 

04-1. 예제 입력 1

5457
3
6 7 8

 
 

04-2. 예제 출력 1

6

 
 

05-1. 예제 입력 2

100
5
0 1 2 3 4

 
 

05-2. 예제 출력 2

0

 
 

06-1. 예제 입력 3

500000
8
0 2 3 4 6 7 8 9

 
 

06-2. 예제 출력 3

11117

 
 

07-1. 예제 입력 4

100
3
1 0 5

 
 

07-2. 예제 출력 4

0

 
 

08-1. 예제 입력 5

14124
0

 
 

08-2. 예제 출력 5

5

 
 

09-1. 예제 입력 6

1
9
1 2 3 4 5 6 7 8 9

 
 

09-2. 예제 출력 6

2

 
 

10-1. 예제 입력 7

80000
2
8 9

 
 

10-2. 예제 출력 7

2228

 
 

11. 힌트

예제 1의 경우 5455++ 또는 5459--
 
 

12. 풀이 및 답

우선 다음과 같은 방법으로 풀어야 한다.

1. |원하는 채널 수 n - 현재 채널 수 100|을 초기 min 값으로 둔다.
   • 현재 채널 100번에서 n번으로 +, - 버튼을 사용해서 이동하는 방법
2. 다른 채널 i로 이동 → 다른 채널 자릿수 + 그 자리에서부터의 거리 = len + |채널 수 n - 다른 채널 i|을 구한다
   • 다른 채널 i로 숫자 버튼을 눌러 이동한 후, 그 자리에서 원하는 채널 n까지 +, - 버튼을 사용해서 이동하는 방법
3. 다른 채널을 입력했을 때의 버튼 누른 횟수가 min보다 작다면 그 값을 min으로 설정한다

 

#include <stdio.h>
#include <math.h>

int broken[11] = { 0 };

int length(int i) {
    if (i == 0) {
        if (broken[0]) return 0;
        else return 1;
    }
    
    int len = 0;
    
    while (i) {
        if (broken[i % 10]) return 0;
        i /= 10;
        len++;
    }
    return len;
}

int main() {
    int n, m, button;
    scanf("%d", &n);    // 이동하려는 채널
    scanf("%d", &m);    // 고장난 버튼 개수
    
    // 고장난 버튼
    for (int i = 0; i < m; i++) {
        scanf("%d", &button);
        broken[button] = 1;
    }
    
    int min = abs(n - 100);
    for (int i = 0; i < 1000000; i++) {
        int len = length(i);
        
        if (len > 0) {
            int tmp = len + abs(n - i);
            if (tmp < min) min = tmp;
        }
    }
    
    printf("%d", min);
}

이동하려는 채널, 고장난 버튼 개수, 고장난 버튼을 차례로 입력받는다.
이동하려는 채널 n에서 100을 뺀 값의 절댓값을 min의 초기값으로 둔다.
i를 0부터 999999까지 증가시키면서 i를 입력할 때 누르는 버튼 횟수(len) + i에서 n까지 +,-를 통해 이동할 때 누르는 버튼 횟수(|n - i|)를 구해 tmp에 저장한다.
만약 tmp가 기존 min값보다 작다면 min값을 tmp로 갱신한다.
 
 

정답!
 

---

 

열심히 풀어봤지만 너무 어려워서 결국 다른 게시글의 도움을 받아 풀었다
더 열심히 공부해야겠다
 
 
 
참고한 게시글
https://juintination.tistory.com/entry/%EB%B0%B1%EC%A4%80-1107%EB%B2%88-%EB%A6%AC%EB%AA%A8%EC%BB%A8

백준 1107번: 리모컨