[Algorithm] 5주차 스터디 - 다이나믹 프로그래밍(백준 11726, 2748, 11053, 11049)

문제 (11726: 2xn 타일링)

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

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제다.

풀이

dp[n] = dp[n-2] + dp[n-1] 점화식을 유추할 수 있다. 

소스코드

n = int(input())

dp = [0 for i in range(1001)]

dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
    
print(dp[n] % 10007)

 

문제 (2748: 피보나치 수 2)

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

2748번: 피보나치 수 2

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하는 문제다.

 

풀이

피보나치 방법을 사용해서 문제를 해결하면 시간 초과로 실패하게 되는 문제다. 피보나치는 재귀 함수를 호출하기 때문에 시간초과가 우려된다. 다이나믹프로그래밍으로 위 문제를 푼다면 arr에 값을 저장하기 때문에 중복 연산이 없어지고, 값을 바로 가져와 시간을 단축할 수 있다.

소스코드

import sys

n = int(sys.stdin.readline())
arr = [0 for _ in range(n+1)]
arr[1] = 1

for i in range(2, n+1):
    arr[i] = arr[i-1] + arr[i-2]

print(arr[-1])

 

문제 (11053: 가장 긴 증가하는 부분 수열)

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

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제다.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

풀이

첫번째 인덱스부터 수열의 길이의 최댓값을 저장하며 첫번째 숫자부터 검사를 해 나간다. 현재 값보다 작은 숫자들 중 가장 큰 길이를 구하는 방법이다. 이 때 길이에 +1을 해주면 된다.

소스코드

n = int(input())

arr = list(map(int, input().split()))
dp = [0 for _ in range(n)]
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

answer = max(dp)
print(answer)

 

문제 (11049: 행렬 곱셈 순서)

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

11049번: 행렬 곱셈 순서

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 이 때 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하는 문제다. 이때, 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

 

풀이

우선, dp라는 2차 행렬을 만들었다.

N~M까지의 최소연산을 dp[n][m] 이라 할 때, dp[0][m] 까지의 최소연산은 (x = 두 행렬을 곱하는 비용)

• dp[0][0]+dp[1][m]+x
• dp[0][1]+dp[2][m]+x

....

• dp[0][m-1]+dp[m][m]+x

중 답이 있을 것임을 풀이에 이용했다.

 

소스코드

# PyPy3

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)] 

for i in range(1, n):
    for j in range(n - i):
        x = j + i
        dp[j][x] = 2 ** 32
        for k in range(j, x):
            dp[j][x] = min(dp[j][x], dp[j][k] + dp[k + 1][x] + arr[j][0] * arr[k][1] * arr[x][1])

answer = dp[0][n-1]
print(answer)