안녕하세요. 모카의 머신러닝 입니다. 이번 포스팅에서는 백준 알고리즘 문제 풀이에 대해 포스팅하도록 하겠습니다.
코드는 이곳을 참고했음을 밝힙니다.
1. 동적 계획법 3
백준 1915번
https://www.acmicpc.net/problem/1915
import sys
input = sys.stdin.readline
D = [[0 for j in range(1001)] for i in range(1001)]
N, M = map(int, input().split())
max = 0
for i in range(0, N):
numbers = list(input())
for j in range(0, M):
D[i][j] = int(numbers[j])
if D[i][j] == 1 and j >0 and i>0:
D[i][j] = min(D[i-1][j-1], D[i-1][j], D[i][j-1]) + D[i][j]
if max < D[i][j]:
max = D[i][j]
print(max*max)
백준 1328번
https://www.acmicpc.net/problem/1328
import sys
input = sys.stdin.readline
mod = 1000000007
N, L, R = map(int, input().split())
D = [[[0 for k in range(101)] for j in range(101)] for i in range(101)]
D[1][1][1] = 1
for i in range(2, N+1):
for j in range(1, L+1):
for k in range(1, R+1):
D[i][j][k] = (D[i-1][j][k]*(i-2) + (D[i-1][j][k-1] + D[i-1][j-1][k])) % mod
print(D[N][L][R])
백준 2342번
https://www.acmicpc.net/problem/2342
import sys
input = sys.stdin.readline
dp = [[[sys.maxsize for k in range(5)] for j in range(5)] for i in range(100001)]
mp = [[0, 2, 2, 2, 2],
[2, 1, 3, 4, 3],
[2, 3, 1, 3, 4],
[2, 4, 3, 1, 3],
[ 2, 3, 4, 3, 1]]
s = 1
dp[0][0][0] = 0
inputList = list(map(int, input().split()))
index = 0
while inputList[index] != 0:
n = inputList[index]
for i in range(5):
if n == i:
continue
for j in range(5):
dp[s][i][n] = min(dp[s - 1][i][j] + mp[j][n], dp[s][i][n])
for j in range(5):
if n == j:
continue
for i in range(5):
dp[s][n][j] = min(dp[s - 1][i][j] + mp[i][n], dp[s][n][j])
s += 1
index += 1
s -= 1
result = sys.maxsize
for i in range(5):
for j in range(5):
result = min(result, dp[s][i][j])
print(result)
지금까지 백준 알고리즘 동적 계획법 3 부분이었습니다.
읽어주셔서 감사합니다. 😃