백준 1107번: 리모컨 (골드5) python

 

백준 1107번 리모컨 문제입니다

 

 

 

현재 채널은 100번이고

리모컨에는 +, -, 0 ~ 9 버튼이 있습니다.

 

입출력입니다.

 

 

이렇게 고장난 버튼과 목표채널을 입력으로 받습니다

 

위 버튼들을 이용하여 최소 횟수로 목표 채널로 가는 수를 구하는 문제입니다

 

알고리즘 분류는 brute force 입니다

 

 

 

---------------------------------------------------------------------------------------------------------------------------------------

 

 

저의 풀이방법입니다.

 

 

1. 숫자 버튼으로 특정 채널로 간 다음에 +또는 - 로 이동하는 방법

2. + 또는 - 만으로 목표 채널까지 가는 방법

 

 

이렇게 두가지로 분류하고 이 값들중에서 최소값을 출력하려고 합니다

 

 

 

첫째 방법은

 

목표 채널에서 +1 또는 -1 하여 해당 채널의 숫자들이 누를수 있는 버튼으로 구성되어있는지 확인합니다.

해당 채널 숫자들이 모두 누를수 있는 버튼일 경우

+1 또는 -1 한 횟수와 해당 채널의 숫자 수를 더한 값을 가져옵니다.

 

그러면 두 가지 값을 반환합니다. +일 경우, - 일 경우

 

 

 

두번째 방법은

 

목표 채널과 현재 채널의 차이값 abs(targetNum - 100) 이렇게 가져올 수 있습니다.

 

 

 

 

이렇게 총 3가지(plus count, minus count, abs값)의 값 가장 적은 값을 출력해주었습니다.

 

 

 

 

아래는 python 코드입니다

 

 

import sys
import math

# 해당 채널의 숫자들이 누를수 있는 버튼으로 구성되어있는지 확인하는 함수
def validation(num,ableBtns):
    if num < 0: return False
    numArray = list(map(int,str(num)))
    isContains: bool = True
    for i in numArray:
        if i not in ableBtns:
            isContains = False
    return isContains

targetNum = int(input())
inputCnt = int(input())

if inputCnt > 0:
    disableBtns = list(map(int,sys.stdin.readline().rstrip().split()))
else:
    disableBtns = []

plusTargetNum: int = targetNum
minusTargetNum: int = targetNum

minusCnt = math.inf
plusCnt = math.inf 

allBtns = [0,1,2,3,4,5,6,7,8,9]
ableBtns = [x for x in allBtns if x not in disableBtns]

answer = abs(targetNum - 100)

while 1:
    if len(ableBtns) == 0: break
        
    if validation(minusTargetNum, ableBtns):
        minusCnt = list(map(int,str(minusTargetNum)))
        minusCnt = (targetNum - minusTargetNum) + len(minusCnt)
        break
    elif validation(plusTargetNum, ableBtns):
        plusCnt = list(map(int,str(plusTargetNum)))
        plusCnt = (plusTargetNum - targetNum) + len(plusCnt)
        break

    minusTargetNum -= 1
    plusTargetNum += 1

print(min(minusCnt,plusCnt,answer))

 

 

 

잘 동작하는 모습

 

 

 

감사합니다

 

 

 

추가적으로 백준에서 수집한 반례 모음집입니다.

 

 

10 
9 
1 2 3 4 5 6 7 8 9
답:11

101
0
답:1

99
10
0 1 2 3 4 5 6 7 8 9
답:1

0
0
답:1

500000
6
0 1 2 3 4 5
답:166672

0
2
0 1
답:3

1555
8
0 1 3 4 5 6 7 9
답:670

944
7
2 3 4 5 6 7 9
답:59

6
9
0 2 3 4 5 6 7 8 9
답:6

500000
10
0 1 2 3 4 5 6 7 8 9
답:499900



101
10
0 1 2 3 4 5 6 7 8 9
답:1

1
9
1 2 3 4 5 6 7 8 9
답:2

99999
1
9
답:7

10
1
0
답:2

0
3
0 1 2
답:4

0
9
0 1 2 3 4 5 6 7 8
답:10

0
10
0 1 2 3 4 5 6 7 8 9
답:100

1
9
1 2 3 4 5 6 7 8 9
답:2

1020
0
답:4

10
2
0 1
답:2

999
1
9
답:5

9990
8
1 2 3 4 5 6 7 8
답:4

123
2
2 3
답:7

199
1 
9
답:4

9
5
9 8 7 6 5
답:3

19
1
1
답:3

//gkfkagkfka12님이 추가해주신 TC
5959
4
1 2 3 4 
4
-----------------------------------------------
56666
0

5
-----------------------------------------------
9999
8
0 1 2 3 4 5 6 7 
4
-----------------------------------------------
10
1
1 
2
-----------------------------------------------
190000
3
1 2 9 
101117
-----------------------------------------------
123
3
1 2 5 
23
-----------------------------------------------
1
9
0 1 2 3 4 5 6 7 8 
9
-----------------------------------------------
100
10
0 1 2 3 4 5 6 7 8 9 
0
-----------------------------------------------
99933
2
3 9 
73
-----------------------------------------------
1023
5
1 2 3 4 0 
27
-----------------------------------------------
91010
2
1 0 
1016
-----------------------------------------------
383399
6
1 2 3 4 5 7 
216607
-----------------------------------------------
6711
2
1 2 
6
-----------------------------------------------
330
4
0 1 2 3 
117
-----------------------------------------------
71923
5
4 5 6 7 9 
8082
-----------------------------------------------
123123
3
1 2 3 
23129
-----------------------------------------------
499999
2
4 8 
7
-----------------------------------------------
1111
9
1 2 3 4 5 6 7 8 9 
1011
-----------------------------------------------
1111
9
0 1 2 3 4 5 6 7 8 
115
-----------------------------------------------
34311
8
0 1 2 3 4 5 6 7 
24316
-----------------------------------------------

49445
7
1 2 3 4 5 6 7 
30560
-----------------------------------------------
933
2
1 2 
3
-----------------------------------------------
1617
3
1 2 3 
621
-----------------------------------------------
856
2
5 6 
10
-----------------------------------------------
1023
8
1 2 3 4 5 6 7 8 
27
-----------------------------------------------
10900
2
1 0 
905
-----------------------------------------------
394344
3
1 2 3 
5662
-----------------------------------------------
99
1
8 
1
-----------------------------------------------
101
9
0 1 2 3 4 5 6 7 8 
1
-----------------------------------------------
2420
6
1 2 3 4 5 6 
1424
-----------------------------------------------
991
1
1 
4
-----------------------------------------------
30002
3
1 3 4 
8
-----------------------------------------------
1698
2
6 9 
6
-----------------------------------------------
499998
3
4 8 9 
8
-----------------------------------------------
1022
5
1 2 3 4 5 
26
-----------------------------------------------

5
10
0 1 2 3 4 5 6 7 8 9
ans95

217
7
0 1 2 4 5 7 8

ans117

---

103
5
2 3 5 7 8

ans3

0
9
1 2 3 4 5 6 7 8 9
ans 1

0
9
1 2 3 4 5 6 7 8 0
ans 10

9
9
1 2 3 4 5 6 7 8 0
ans 1

140200
3
4 5 6
ans 207

1555
3
0 1 9
ans 670

99999
9
0 2 3 4 5 6 7 8 9
ans 11118

50000
9
0 1 2 3 4 5 6 7 8
ans 40005

139133
7
9 6 8 2 1 5 7
ans 94694

14
2
1 5
ans 6

889
9
0 2 3 4 5 6 7 8 9
ans 226

6
7
3 4 5 6 7 8 9
ans 5

88
2
8 9
ans 12

7
7
3 4 5 6 7 8 9
ans 5

0
0
ans 1

1
9
0 1 2 3 4 5 6 7 8
ans 9

1705
2
6 7

정답 : 99

1717
1
7

정답 : 22

2
8
1 2 3 4 5 6 7 8

정답: 3

2
7
1 2 3 4 6 8 9

정답: 3

1
8
1 2 3 4 5 6 7 8

정답: 2

1
7
1 2 4 5 7 8 9

정답: 2

1555
8
0 1 3 4 5 6 7 9
670
    
101
3
4 5 6
1
    
162
9
0 1 3 4 5 6 7 8 9
62
    
10
9
1 2 3 4 5 6 7 8 9
11
    
1
10
0 1 2 3 4 5 6 7 8 9  
99
    
1
1
1
2
    
0
9
1 2 3 4 5 6 7 8 9
1
    
101
0
1
    
100000
9
0 1 2 3 4 5 6 7 8
6
    
1
10
0 1 2 3 4 5 6 7 8 9
99
    
1111
9
1 2 3 4 5 6 7 8 9 
1011
    
2229
6
4 5 6 7 8 9
5
    
10
1
0
2
    
0
10
0 1 2 3 4 5 6 7 8 9
100
    
9
8
0 3 4 5 6 7 8 9
4
    
0
3
0 1 2
4

99999

9

0 2 3 4 5 6 7 8 9

답 : 11118

50000

9

0 1 2 3 4 5 6 7 8

답 : 40005

9

9

1 2 3 4 5 6 7 8 9 

답 : 10