https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
- 채널이 50만번까지 있지만, 채널 버튼을 누르는건 500000을 누르더라도 5, 0, 0, 0, 0, 0 6번밖에 되지 않기 때문에 브루트포스를 사용해 구할 수 있음을 캐치해야했던 문제
- 처음엔 누를 수 있는 채널들 중 가장 주어진 채널 값과 가장 가까운 값을 한번에 찾는 방법을 생각해 그리디 알고리즘으로 풀어보려고 했지만, 계속 반례가 등장하는 바람에 포기할 수 밖에 없었다.
** 주요 포인트 **
- 그리디 알고리즘으로 풀 경우 자릿수가 변하는 경우도 체크를 해주어야 했고, 낮은 값에서 올라가는게 유리한지, 높은 값에서 내려가는게 유리한지도 체크를 해주어야 했다.
- 자릿수도 자릿수를 늘린 뒤 줄여 가는 방법 ex) 999로 가기 위해 1000에서 내려가기, 자릿수를 줄인 뒤 늘려가는 방법 ex) 9에서 11로 가기, 같은 자릿수더라도 작은 숫자에서 올리기 ex) 8000으로 가기위해 9221 을 눌러야 하는 경우가 있고 7779를 눌러야 하는 경우가 있다.
- 로직이 잘못된 걸 수도 있지만 이 경우들을 고려해주어도 계속 놓치는 반레들이 생겨났고, 결국 브루트포스로 문제를 풀 수 밖에 없었다
- 채널 100번에서 시작하므로 버튼을 가장 많이 누르게 되는 경우(모든 숫자가 고장났을 경우) 채널 최댓값인 50만까지 가는데 49900이 들게 되지만 50만에서 시작할 경우 0까지 탐색을 해주기 위해서 그냥 반복을 50만번 수행하도록 했다.
코드 공유
더보기
S = input()
N = int(input())
ans = -1
min_ans = 9999999
if N != 0 :
n_lst = list(map(int, input().split()))
move = 0
for move in range(500000) :
plus_number = int(S) + move #채널 하나를 올려보고 그곳에서 접근할 수 있는지 체크
minus_number = int(S) - move #채널 하나를 내려보고 그곳에서 접근할 수 있는지 체크
for i in str(plus_number): # 해당 채널에 이동이 가능하다면 더 move할 필요없이 break
if int(i) in n_lst :
break
else :
plus_number = abs(int(S) - plus_number) + len(str(plus_number))
min_ans = min(min_ans, plus_number)
if minus_number >= 0 :
for i in str(minus_number):
if int(i) in n_lst:
break
else :
minus_number = abs(int(S) - minus_number) + len(str(minus_number))
min_ans = min(min_ans, minus_number)
move +=1
else :
min_ans = len(S)
print(min(abs(100-int(S)), min_ans)) # 100에서 이동하는 것과 구해놓은 채널에서 이동하는 것중 작은 값 출력'알고리즘 스터디' 카테고리의 다른 글
| 백준 22856. 트리 순회 - 파이썬 (0) | 2023.03.01 |
|---|