[python code review] 5주차 (계단 오르기, 리모컨, 나무 자르기)

[계단 오르기] (중하)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

n = int(input())
stairs = [int(input()) for _ in range(n)]
# dp[x] : x 번째 계단까지 이동했을 때의 최대 점수
dp = [0]*(n+1)

def dynamic():
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    for i in range(2, n):
        # i-2번째에서 i번째 계단을 밟는 경우
        dp[i] = max(dp[i], dp[i-2] + stairs[i])
        # i-1번째에서 i번째 계단을 밟는 경우
        dp[i] = max(dp[i], dp[i-3]+stairs[i-1]+stairs[i])

if n == 1:
    print(stairs[0])
elif n == 2:
    print(stairs[0] + stairs[1])
else:
    dynamic()
    print(dp[n-1])

오랜만에 dp 문제를 풀려고 하니까 접근법이 생각나지 않아 막막했다. 아래 블로그를 참고하여 점화식을 세우면서 문제를 풀 수 있었다! 앞으로 dp문제를 풀 때 이처럼 DAG로 모델링하여 접근하면 좋을 것이다. 

https://www.secmem.org/blog/2020/10/24/dp/

동적 계획법을 사이클이 없는 유향 그래프(DAG) 로 모델화하는 방법

 

DAG(DP를 모델화한 그래프) 구성 요소

• 정점: 문제에서의 특정 상황을 유일하게 결정지을 수 있는 변수들로 이루어진 상태
• 간선: 상태간의 전이를 나타내는 점화식

1) 각 정점은 자신의 상태에 대한 답을 갖는다.

2) 각 상태에서의 답을 나타내는 변수(배열)는 흔히 dp라고 선언, 상태를 구성하는 변수는 순차적으로 배열의 각 차원을 담당

=> 상태를 구성하는 두 변수가 x, y라면 dp[x][y]와 같은 형태로 특정 상태의 답을 나타내는 방식.

 

점화식: 하나의 상태가 결정되기 위해 먼저 결정되어야 하는 다른 상태들과의 관계를 나타내는 식

ex) dp[x]=max(dp[x−1],dp[x−2])dp[x]=max(dp[x−1],dp[x−2])

     dp[x]dp[x]가 결정되기 전에 먼저 결정되어야 하는 상태: dp[x−1]dp[x−1], dp[x−2]dp[x−2]

기저 상태: 다른 상태와의 관계로 표현되지 않고 특정 상수를 답으로 가지는 상태

 

3) 그래프 내에 사이클이 없어야 한다.

 

문제 풀이 접근 방식

1) dp[x] 설정 # dp[x] : x 번째 계단까지 이동했을 때의 최대 점수

2) dp[x]를 구하기 위한 점화식 

 # i-2번째에서 i번째 계단을 밟는 경우
   dp[i] = max(dp[i], dp[i-2] + stairs[i])
 # i-1번째에서 i번째 계단을 밟는 경우
   dp[i] = max(dp[i], dp[i-3]+stairs[i-1]+stairs[i])

 

[리모컨] (중상)

https://www.acmicpc.net/problem/1107

1107번: 리모컨

1. 구현

def broken(number):
    for N in str(number):
        if N in unable:
            return True
    return False

channel = int(input())
answer = abs(100-channel)
n = int(input())
unable = set()
if n:
    unable = set(input().split())
for num in range(1000001):
    if not broken(num):
        answer = min(answer, len(str(num)) + abs(num-channel))
print(answer)

잘 모르겠어서 블로그를 참고했다. 이런 식의 brute force는 잘 생각이 나질 않는다. 당연히 시간초과가 날 거라는 생각때문일지도.... 시간초과를 발생하지 않는 범위를 생각해보는 습관을 들여야겠다.  

 

[틀린풀이]

def pushButton():
    result = []
    for c in channel:
        s, e = -1, +1
        if c in button:
            result.append(c)
            continue
        while s <= e:
            if c+s in button:
                result.append(c+s)
                break
            elif c+e in button:
                result.append(c+e)
                break
            else:
                s -= 1
                e += -1
    return result


# 현재 보고 있는 채널 번호 100
channel = list(map(int, input())) # 이동하고자 하는 채널
# print('channel', channel)
n = int(input())
unable = [] # 누를 수 없는 버튼
if channel == 100:
    print(0)
elif n == 0:
    print(len(channel))
else:
    unable = list(map(int, input().split()))
    button = [i for i in range(10) if i not in unable]
    r = pushButton()
    answer = len(r) + abs(int(''.join(map(str, r))) - int(''.join(map(str, channel))))
    print(answer)

test case 7번에서 틀림. [8,0,0,0,0]에 대해 pushButton 함수에서 [7,7,7,7,7]을 반환해야 하는데 [7,0,0,0,0]을 리턴함

 

[나무 자르기] (중하)

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

# 나무의 수, 가져오려고 하는 나무 길이
n, m = map(int, input().split())
height = list(map(int, input().split()))
result = 0

def findMaxHeight(arr, start, end):
    global result

    if start > end:
        return
    while start <= end:
        mid = (start + end)//2
        total = 0
        for h in height:
            if h > mid:
                total += h - mid
        # 가져오려는 나무 길이(m)보다 길거나 같다면
        if total >= m:
            # 절단 높이를 키워야
            start = mid + 1
            result = max(result, mid)
        # 가져오려는 나무 길이(m)보다 짧다면
        else:
            # 절단 높이를 줄여야
            end = mid - 1

findMaxHeight(height, 0, max(height))
print(result)

기본적인 이분탐색 문제다. 다음 주차에 더 딥한 문제를 풀이하고 싶어 가져왔다 :-)

유사문제 : 랜선 자르기 https://www.acmicpc.net/problem/1654