코드

n = int(input())
m = int(input())

# 무식하게 +나 - 버튼으로만 이동한 경우 => 사실상 최댓값
answer = abs(100-n)

if m:
    # 고장은 숫자버튼만 발생
    breakdown = list(map(int, input().split()))
else:
    breakdown = []

# 채널 자체는 무한대 => n보다 큰 값에서부터 내려와서 답을 도출하려고 할 때
# 예를 들어 찾고자 하는 채널이 50만인 경우
# 50만보다도 더 큰 채널에서부터 내려와서 50만 채널에 도착하는 경우가
# 100번에서부터 올라가는 경우보다 작은 경우가 분명 발생
# 100만에서 50만까지 50만번 - 버튼을 클릭하는 경우가 최대 경우일 것이므로
# 이를 넉넉하게 모두 처리하기 위해서 범위를 100만으로 설정

# i => 숫자 버튼만 눌러서 n과 최소의 차이로 도달할 수 있는 채널
for i in range(1000001):
    
    # 고장 체크
    break_check = False
    for j in str(i):
        
        # 고장난 버튼이라면 break
        if int(j) in breakdown:
            break_check = True
            break
            
    # 파이썬에선 굳이 안 해줘도 되는 코드
    # 다른 언어로 풀 때 사용할 수도 있으므로 그냥 적음
    if break_check:
        continue
    # 고장이 한 번도 발생하지 않은 경우에 실행
    else:
        # 찾은 문자열의 길이 + 그 값에서 찾고자하는 채널 - n을 더하면
        # 최소 횟수로 이동한 거리가 된다
        answer = min(answer, len(str(i)) + abs(i - n))

print(answer)

문제 해설

구글링으로 도움을 대단히 많이 받았다… 브루트포스 문제에 정말 약한가보다 ㅠㅠ

주석에도 적어놨지만 문제를 푸는데 어려웠던 점을 별도로 정리해보겠다.

  1. 처음에 DP로 접근하려고 했으나 규칙이 파악되지 않음

  2. 최소 횟수를 구하라길래 BFS로 구현하려고 했으나 그래프가 그려지지가 않음

  3. 브루트포스로 접근 시도

    1. 범위 설정

      • 생각해보니 50만보다 큰 채널에서부터 내려오는 경우가 발생
      • 최악의 경우 50만까지 최대 40만번은 -버튼 눌러서 내려오는 경우…
      • 따라서 범위를 넉넉하게 100만까지 설정

    2. 찾고자 하는 숫자의 매 자리마다 숫자 버튼으로 클릭

      • # i => 숫자 버튼만 눌러서 n과 최소의 차이로 도달할 수 있는 채널
for i in range(1000001):
            
    # 고장 체크
    break_check = False
    for j in str(i):
                
        # 고장난 버튼이라면 break
        if int(j) in breakdown:
            break_check = True
            break

      • 이 부분인데, i 값을 찾을 때, i의 각 자리값(숫자 버튼)을 어떤 식으로 처리해줘야 할지 파악 못 함

      • i를 문자열로 바꾼 후, 각각의 문자열이 breakdown(고장난 버튼)에 포함되는가를 확인

    3. 고장이 발생하지 않은 경우

      • answer = min(answer, len(str(i)) + abs(i - n))

      • 위의 식은 쉽게 구했지만, 이를 어떤 경우에 적용해줘야 하는지 파악을 못 함

      • 고장 자체가 없는 경우 항상 이 식이 실행되게 하면 된다

      • 어차피 최솟값은 한 번 잡히면 변경되지 않을 것이기 때문에

브루트포스 문제는 정말 완전 무식 탐색이기 때문에 무의식 적으로 스스로 이런 풀이 방법을 배제하는 거 같다. 좀 더 다양한 문제를 열린 태도로 접근하여 푸는 연습을 해야겠다…ㅠㅠ

댓글남기기

참고