1. 경우의 수로 풀기 (2022.01.13)
많은 조건을 꼼꼼히 따져봐야 풀 수 있는 문제였다. 다른 분이 올려주신 반례 모음집이 문제를 푸는 데 많은 도움이 됐다.
발상 자체는 단순하다. 누를 수 있는 숫자로 최대한 목표 채널과 가까운 값을 만든 후 증감 버튼으로 조정하는 횟수를 세면 된다. 총 5가지의 경우를 생각해 보았다.
- 증감 버튼만 눌렀을 때
- 목표 채널보다 크면서 가장 가까운 값에서 감소시킬 때
- 목표 채널보다 작으면서 가장 가까운 값에서 증가시킬 때
- *목표 채널보다 한 자리 큰 수 중 최솟값에서 감소시킬 때
- *목표 채널보다 한 자리 작은 수 중 최댓값에서 증가시킬 때
예를 들어 목표 채널이 5457이고 6, 7, 8번이 고장났다면 2는 5455, 3은 5459, 4는 10000, 5는 999이다.
2와 3을 구할 때는 일단 목표 채널과 동일한 숫자를 지정하다가, 어떤 숫자가 고장나서 동일한 값을 쓸 수 없을 때 근삿값을 대신 넣고 해당 근삿값의 대소 여부에 따라 나머지 자릿수를 채운다. 근삿값 자체가 범위(0~9)를 벗어나 넣을 수 없는 상황이라면 앞 자릿수로 이동하여 근삿값을 구하는 것을 반복한다.
1~5에 해당하는 값 중 결과를 최소로 만드는 것을 출력해주면 된다.
import sys
input = sys.stdin.readline
broken = [False] * 10
N = int(input())
M = int(input())
if M > 0:
for i in list(map(int, input().split())):
broken[i] = True
MAX = 0
MIN = 0
for i in range(9, -1, -1):
if not broken[i]:
MAX = i
break
for i in range(1, 10, 1):
if not broken[i]:
MIN = i
break
def count_channel():
if N == 100:
return 0
if M == 10:
return abs(N - 100)
upper_bound = "" # N보다 1자리 큰 수 중에서 최솟값
lower_bound = "" # N보다 1자리 작은 수 중에서 최댓값
if not broken[0]:
upper_bound = str(MIN) + "0" * len(str(N))
else:
upper_bound = str(MIN) * (len(str(N)) + 1)
if len(str(N)) > 1:
lower_bound = str(MAX) * (len(str(N)) - 1)
else:
lower_bound = "0" if not broken[0] else str(MIN)
bound = min(
len(upper_bound) + abs(N - int(upper_bound)),
len(lower_bound) + abs(N - int(lower_bound)),
)
res_upper = ""
res_lower = ""
for d in str(N):
if broken[int(d)]:
break
res_upper += d
res_lower += d
# 상한값 계산
idx = len(res_upper) if res_upper else 0
flag = True
while flag and 0 <= idx < len(str(N)):
for i in range(int(str(N)[idx]) + 1, 10):
if not broken[i]:
res_upper = res_upper[:idx] + str(i)
while len(res_upper) < len(str(N)):
res_upper += "0" if not broken[0] else str(MIN)
flag = False
break
idx -= 1
if not res_upper:
if not broken[0]:
res_upper = str(MIN) + "0" * len(str(N))
else:
res_upper = str(MIN) * (len(str(N)) + 1)
# 하한값 계산
idx = len(res_lower) if res_lower else 0
flag = True
while flag and 0 <= idx < len(str(N)):
for i in range(int(str(N)[idx]) - 1, -1, -1):
if not broken[i]:
res_lower = res_lower[:idx] + str(i)
while len(res_lower) < len(str(N)):
res_lower += str(MAX)
flag = False
break
idx -= 1
if not res_lower:
if len(str(N)) > 1:
res_lower = str(MAX) * (len(str(N)) - 1)
else:
res_lower = "0" if not broken[0] else str(MIN)
return min(
abs(N - 100),
bound,
len(str(int(res_upper))) + abs(N - int(res_upper)),
len(str(int(res_lower))) + abs(N - int(res_lower)),
)
print(count_channel())
2. 브루트 포스로 풀기 (2023.08.17)
그동안 풀었던 PS 문제 코드들을 깃허브에 정리하다가 우연히 이 문제를 다시 보게 되었는데, 위처럼 일일이 모든 경우에 대한 처리 방법을 구현하지 않고도 브루트 포스 기법으로 매우 단순하게 풀 수 있음을 깨닫게 되었다.
이동하려는 채널의 범위가 최대 50만이고, 그 위쪽에서 감소 버튼을 통해 내려가는 경우를 고려하기 위해 가능한 채널의 범위를 최대 100만까지로 잡는다. 그리고 각 채널의 자릿수를 하나씩 보면서 고장난 버튼인지 아닌지를 판단하므로 가장 긴 자릿수는 100만 = 1000000의 7자리가 된다.
즉, 1000000 * 7 < 10000000이므로 다른 연산들을 고려하더라도 제한 시간 2초 안에 충분히 해결할 수 있다. (왜 작년엔 브루트 포스로 풀 생각을 못 했을까...?)
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
DIGIT = set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
if M == 0: # 고장난 숫자가 없다면 한 번에 이동
print(min(len(str(N)), abs(N - 100)))
exit(0)
brokenDigit = set(input().rstrip().split())
result = abs(N - 100)
if M == 10: # 모든 숫자가 고장났다면 증감 버튼을 통해서만 이동
print(result)
exit(0)
for inter in range(1000001):
reachable = True
for digit in str(inter):
if digit in brokenDigit: # 현재 채널 값에 고장난 숫자가 포함된 경우
reachable = False
break
if reachable:
result = min(result, len(str(inter)) + abs(inter - N)) # 숫자 버튼 누르기 + 증감버튼 누르기
print(result)