[TIL] 동적 프로그래밍 문제 풀이2

1. 11049번 - 행렬 곱셈 순서

1. 최적 괄호 묶기의 구조

    : n개의 행렬을 어떻게 곱할지 애매함을 없애기 위해 괄호로 묶는다.

      ex) ((A1, A2), A3) or (A1, (A2, A3))

  이 문제는 n개의 행렬들의 체인 <A1, A2, ... , An>이 주어졌을 때 A1, A2, ... , An의 스칼라 곱의 개수를 최소화 하도록 괄호를 묶어라! 라고 하는 것과 같다. 

• AiAi+1...Aj를 괄호호 최적으로 묶기 위해 Ak Ak+1의 사이에서 나눈다고 가정
  • AiAi+1...Ak
  • Ak+1Ak+2...Aj
  • 위의 두 부분문제는 각각 최적 괄호 묶는 방법이 되어야 한다.

2. 재귀해

• i == j 일 경우 0
• i < j 일 경우 → k, k+1로 나눈다.
  • Ai = pi-1 * pi 라면
  • Ai..kAk+1..j = pi-1 *pk * pj

3. 구현

import sys

N = int(sys.stdin.readline())
# matrix[i][0] : i번째 행렬의 행의 수 / matrix[i][1] : i번째 행렬의 열의 수
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# dp[i][j] = Ai...j 행렬의 최소 연산 횟수
dp = [[0] * N for _ in range(N)]

# l : 행렬 체인 길이 (행렬은 최소 1개)
for l in range(1, N) :
    for i in range(N-l): # 행렬 곱셈의 시작 행렬 인덱스
        j = i+l # 행렬 곱셈의 끝 행렬 인덱스
        dp[i][j] = float('inf')
        for k in range(i, j) : # i ~ j 사이를 k로 나눈다.
            q = dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k+1][0] * matrix[j][1]
            if q < dp[i][j] :
                dp[i][j] = q

# 첫번째 행렬부터 마지막 행렬까지의 최소 연산 횟수
print(dp[0][N-1])

생각하는 것도 어려웠지만, 구현하는 것조차 어려웠던 문제
이번에도 알고리즘 책을 참고하고 블로그를 참고했다.

< 참고 블로그 > https://rccode.tistory.com/entry/Python-백준-11049번-행렬-곱셈-순서

---

2. 11053번 - 가장 긴 증가하는 부분 수열

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] * N
dp[0] = 1 # 기저값
for i in range(1, N) :
    t = 0 # 현재 A[i]의 값보다 작은 값들 중 가장 큰 값의 dp 저장
    for j in range(i) :
        if A[i] > A[j] and t < dp[j] :
            t = dp[j]
    dp[i] = t + 1

print(max(dp))

이전에 이분 탐색으로 풀었던 문제라 어느 정도 감을 잡고 풀었다. 확실히 저번보다는 쉬웠다.
대신 효율은 저번 코드가 더 좋았다.

dp[i] = i번째 수보다 작은 수들이 증가 수열의 길이
< 알고리즘 > https://namu.wiki/w/최장%20증가%20부분%20수열

---

3. 2253번 - 점프

import sys

N, M = map(int, sys.stdin.readline().split())
small = [int(sys.stdin.readline()) for _ in range(M)]

# 만약 막히지 않고 속도가 계속 증가하면 가능한 속도
max_speed = int((2*N)**(1/2)) + 1

# dp[i][j] = i 속도로 j번 돌로 온 최소 횟수
dp = [[float('inf')] * (max_speed+1) for _ in range(N+1)]

# 문제 조건 상 무조건 2번에 처음 움직여야하는데
# 2번 돌이 너무 작으면 애초에 이동 불가능
if 2 not in small :
    dp[2][1] = 1 # 기저값
    for num in range(3, N+1) : #3번 돌부터
        if num not in small : # 올라갈 수 있는 돌이면
            for speed in range(1, max_speed) :
                # 1. num-speed = 전 위치
                # 2. 각각 현재 속도의 -1, 0, +1 만큼의 이동 횟수를 가져온다.
                # 3. 가장 작은 값에 +1
                dp[num][speed] = min(dp[num - speed][speed - 1], dp[num - speed][speed], dp[num - speed][speed + 1]) + 1

ans = min(dp[N])
if ans == float('inf') : # 도달 못함
    print(-1)
else :
    print(ans)

오늘 푼 문제 중 가장 풀 때 감이 안잡힌 문제였다.
우선 동료분의 설명을 듣고 해보려고 했지만 결국 코드를 참고하여 풀었다.
< 참고 코드 > https://github.com/emplam27/Python-Algorithm/blob/master/백준/백준_2253_점프_DP_2차원.py

최대 속도 구하는 방식

등차 수열의 특성을 이용해서 구한 것이다.
등차 수열의 합 = k(2a + (k-1)d) / 2
(a : 수열의 시작 값 / d : 공차 = 수열이 얼마씩 증가하는지 / k : 몇번 째 수열 요소인지)
우리가 구해야할 값은 도착해야할 돌까지 계속해서 속도가 증가할 때 얼마까지 가능한지이다.
그러므로 k(2a + (k-1)d) / 2 = N 으로 두고 a,d = 1, 1이므로
k(k+1) = 2N 이라는 식이 나오고
이를 k로 정리하면 k = (2N-k)**0.5 이다.
제곱근을 계산할 때 상수는 거의 영향을 주지 않으므로 k를 뺄 수 있다.
우리가 이를 코드로 구현할 때는 소수점을 버린 정수를 사용하므로 +1 까지 해준다.

dp 배열은 행으로는 돌의 번호, 열로는 이동 속도를 지정하여 저장한다.
즉, dp[i][j] = i번째 돌에 j 속도로 오는 최소 이동 횟수를 저장한다.

위의 참고 코드는 다 괜찮은데 한가지 예외 처리가 필요하다.
예시 )
3 1
2

결과 ) -1

이는 2번 돌에 바로 갈 수 없을 경우로 이 때를 예외처리해 줄 필요가 있다.