반응형
문제설명
https://www.acmicpc.net/problem/1107
사고과정
- 중복을 허용하는 순열 product 라이브러리를 활용하려고 노력했다. 문제에서 잡아내야 할 포인트들은 다음과 같다.
- 1. 고장난 숫자 버튼을 제외하고 숫자 순열 경우의 수를 만든 후 +/- 를 사용해서 원하는 채널로 가기
- 2. 시작채널 100으로부터 +/-만 사용해서 원하는 채널로 가기
- 3. 문제에서 채널은 무한대까지 있다고 했다. 이를 캐치해야 했어야 함. 주어지는 채널 수 범위는 50만이지만 움직일 수 있는 채널은 무한대까지 이기 때문에 50만 채널에 도달하는 방법이 오름차순으로 도달하는 방법도 있지만 50만 1에서 50만으로 가는 내림차순으로 도달하는 방법도 있다.
- 약 1시간 반정도 풀려고노력했는데, 어떤 반례에서 테스트를 통과하지 못하는지 찾지 못했다. 질문 게시판을 다 뒤져가면서 찾아보았는데도 못 찾았다. 질문 게시판에 있는 반례는 다 맞았는데..
- 그래서 구글링을 해서 풀이를 보았는데 매우 간결한 풀이를 보았다. 이 분은 product를 사용하는 것이 아니라 일반 for loop 숫자를 0부터 100만(이 때, 100만으로 설정한 이유는 50만 채널에 도달하기 위해서 내림차순으로 가기 위함!)으로 설정했는데, 이 때 loop도는 숫자를 '채널 번호'라고 세운 것! 이게 정말 인상적이었다.
- Loop를 돌면서 해당 채널 번호에 사용된 숫자 버튼들이 주어진 고장난 버튼 숫자 목록안에 속한다고 하면 바로 False를 리턴해서 그냥 시작 채널에서 +/-만 사용하도록 처리해주었다. 어차피 최소버튼 개수만 구하면 되므로 그렇게 처리한 듯하다.
- 대단한 풀이들이 정말 많은 듯 하다...
풀이(스스로 못 푼 풀이)
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
broken = list(input().rstrip())
# 시작 채널 100에서 + 또는 - 만 사용할 경우
result = abs(n - 100)
def check(channel):
channel = list(str(channel))
for c in channel:
# 채널 숫자버튼이 하나라도 고장난 버튼이라면 False
if c in broken:
return False
return True
# i가 채널이라고 가정 -> 100만까지 도는 이유: 채널을 50만 넘어가게 한다음 -채널 하는게 더 적은 경우도 있음
for i in range(0, int(1e6)+1):
if check(i):
result = min(result, len(str(i)) + abs(n - i))
print(result)
반응형
'알고리즘 삽질장' 카테고리의 다른 글
[BOJ] 6064번 - 카잉 달력 (0) | 2021.11.05 |
---|---|
[BOJ] 14500번 - 테트로미노 (0) | 2021.11.05 |
[BOJ] 1476번 - 날짜 계산 (0) | 2021.11.03 |
[BOJ] 3085번 - 사탕 게임 (0) | 2021.11.03 |
[BOJ] 2309번 - 일곱 난쟁이 (0) | 2021.11.03 |