리모컨 - 파이썬(DP)

사이트 링크 : https://codeup.kr/problem.php?id=3120&rid=0

 

문제는 아래와 같습니다.

문제

컴퓨터실에서 수업 중인 정보 선생님은 냉난방기의 온도를 조절하려고 한다.

냉난방기가 멀리 있어서 리모컨으로 조작하려고 하는데, 리모컨의 온도 조절 버튼은 다음과 같다.

1) 온도를 1도 올리는 버튼

2) 온도를 1도 내리는 버튼

3) 온도를 5도 올리는 버튼

4) 온도를 5도 내리는 버튼

5) 온도를 10도 올리는 버튼

6) 온도를 10도 내리는 버튼

이와 같이 총 6개의 버튼으로 목표 온도를 조절해야 한다.

현재 설정 온도와 변경하고자하는 목표 온도가 주어지면 이 버튼들을 이용하여 목표 온도로 변경하고자 한다.

이 때 버튼 누름의 최소 횟수를 구하시오.

예를 들어, 7도에서 34도로 변경하는 경우,

7 -> 17 -> 27 -> 32 -> 33 -> 34

이렇게 총 5번 누르면 된다.

입력

• 현재 온도a 와 목표 온도b가 입력된다. ( 0 <= a , b <= 40 )

출력

• 최소한의 버튼 사용으로 목표온도가 되는 버튼의 횟수를 출력한다.

문제 해결 포인트 

• 문제의 조건중 반례가있어 생각을 많이 했던 문제였습니다.
• 앞으로 한 방향으로만 가는것을 생각했던 저는 b<a 인경우와 23,31 처럼 한 방향으로 갔다가 반대 방향으로 가는 경우가 있었습니다.
• 우선 반대 방향으로 가는경우가 문제였는데 23,31 인 경우 23->33->32->31 되어서 답은 3입니다.
• 처음 생각했던 조건인 n+10 <= b 는 23 -> 33 으로 가지 못해서 n+6 <= b 로 가졌갔습니다.
• 조건은 10번은 (5+1) 5번은 (1+1) 2 로 두었습니다. 그 이유는 뒤로 가는 경우를 체크하기 위해서 입니다. 
• DFS 와 DP 테이블을 적절히 섞어서 풀어내기는 했지만 아직 코드 정리가 덜된것 같아 리팩토링후 다시 풀어봐야겠습니다.

정답코드 

a, b = map(int, input().split())

max_value = max(a, b)
min_value = min(a, b)
dp = [max_value for _ in range(max_value+100)]

dp[b] = 0

def dfs(n):
    if not (0 <= b <= b+10):
        return 0
    if dp[n] != max_value:
        return dp[n]
    if b == n:
        return dp[n]
    if n < b:
        if n + 6 <= b:
            dp[n] = min(dp[n], dfs(n+10)+1)
        if n + 2 <= b:
            dp[n] = min(dp[n], dfs(n+5)+1)
        if n + 1 <= b:
            dp[n] = min(dp[n], dfs(n+1)+1)
    else:
        if n - 1 >= b:
            dp[n] = min(dp[n], dfs(n-1)+1)
        if n - 2 >= b:
            dp[n] = min(dp[n], dfs(n-5)+1)
        if n - 6 >= b:
            dp[n] = min(dp[n], dfs(n-10)+1)
    return dp[n]


dfs(a)
print(dp[a])

 

해당 문제는 계속 리뷰를 해서 코드를 정교화 해보는것도 좋은것 같습니다.