백준 1107번 리모컨

문제

: 리모컨에는 버튼이 0부터 9까지의 숫자와 +,-로 되어있다.
+,-는 1씩 이동하며 채널은 0아래로 내려가지 않는다. 이동하고자 하는 채널 N이 주어지고 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 물러야하는지 구하는 프로그램을 작성하시오. 현재 보고있는 채널은 100번이다.

입력 & 출력

• 첫째 줄에 이동하고자 하는 채널 N이 주어진다. (0<=N<=500,000)
• 고장난 버튼의 개수 M (0<=M<=10) 이 주어진다.
• 고장난 버튼이 있는 경우에 해당 버튼이 주어진다.

풀이

: 채널에 접근하는 방법의 수는 3가지이다.

• 직접 입력하기
• +,-만으로 이동하기
• 최대한 가까운 수로 이동 후 +,- 동작으로 이동하기

1. 직접 입력하기

: 주의 할 점은 고장난 수가 있으면 직접 입력이 불가능하다는 것이다. 이를 위해 변수하나를 식별자로 사용하였다.

# check number
token = True
for i in N:
    i = int(i)
    if i in broken:
        token = False
        break
if token:
    clicks.append(len(N))

2. +,- 만으로 이동하기

# 2. +,- 만으로 이동하기
clicks.append(abs(int(N)-now))

3. 가까운 수로 접근 후 +,-동작하기

: 역으로 +,-를 진행 후에 부서지지 않은 수로 완성할 수 있는지를 판별하였다.

• 우선 +,-를 수행하는데 +,-의 수행 횟수와 이동된 수의 버튼 클릭수의 합이 위의 1,2번의 최솟값보다 작아야 의미가 있다고 생각하였다.
• 수행 과정에서 위의 제한 조건이 맞는 수들에 대해 부서지지 않은 버튼으로 생성이 가능한지 확인해주었다.

# 1,2번 과정의 결과
limit = min(clicks)

up_count=0
up = int(N)
down_count=0
down = int(N)
# up,down 두 경우 판별해야한다.
while up_count+len(str(up))<limit:
    token = True
    up_count+=1
    up+=1
    for i in str(up):
        if int(i) in broken:
            token = True
            break
        else:
            token = False
    if not token:
        limit = up_count+len(str(up))
        break
while down_count+len(str(down))<limit and down>0:
    token = True
    down_count+=1
    down-=1
    for i in str(down):
        if int(i) in broken:
            token = True
            break
        else:
            token = False
    if token == False:
        limit = down_count + len(str(down))
        break

느낀점 및 참고

: 처음 문자열로 접근하였을 때 오히려 어렵게 풀이했던 것 같다. 아이디어를 생각하는 것이 생각보다 오래걸려 아쉬웠다.

문제 링크 : https://www.acmicpc.net/problem/1107
깃헙 코드 : https://github.com/poriz/baekjoon/blob/master/codes/1107.py