https://www.acmicpc.net/problem/1983
1983번: 숫자 박스
첫 줄에는 숫자 박스의 열의 수를 나타내는 정수 N(1 ≤ N ≤ 400)이 주어진다. 그 다음 두 줄에는 각각 숫자 박스의 위와 아래의 행에 놓인 초기 숫자판들의 숫자가 하나 이상의 공백을 두고 나타
www.acmicpc.net
백준 - 숫자 박스 (1983번) (counting ones)
난이도 : Gold 2
알고리즘 : Dynamic Programming
Time Complexity : O( N ^ 3 )
import sys
input = sys.stdin.readline
def check(i, r, c):
maxy = 0
if 0 <= i-r < erl and 0 <= i-c < ecl:
maxy = memo[r][c] + row[i-r]*col[i-c]
if 0 < r:
maxy = max(maxy, memo[r-1][c])
if 0 < c:
maxy = max(maxy, memo[r][c-1])
memo[r][c] = maxy
if __name__ == '__main__':
N = int(input())
row = [r for r in map(int, input().split()) if r]
col = [c for c in map(int, input().split()) if c]
rl = N-len(row)+1
cl = N-len(col)+1
erl, ecl = len(row), len(col)
memo = [[0]*cl for _ in range(rl)]
for i in range(N):
for r in range(rl-1, -1, -1):
for c in range(cl-1, -1, -1):
check(i, r, c)
print(max(max(row) for row in memo))
DP를 적용하기 정말 까다로운 문제였다.
예제 1번에서 0을 모두 제거해보면 아래와 같은 수열이 된다.

N = 7 이었으므로, i는 0~6까지 7번 진행한다.
r과 c의 원래 0의 개수가 2개, 2개이므로
행렬 M의 크기는 (2+1)*(2+1)이 된다.
0행 0열이면, 현재까지 0을 중간에 하나도 끼지 않은 것이고
x행 y열이면, 현재까지 r에는 0을 x번, c에는 0을 y번 끼운 것이다.
각 i번째 연산에서,
가장 아래 행부터 시작해서 위로 올라간다.
각 행에서는 오른쪽에서 왼쪽 방향으로 연산을 진행한다.
i번째 연산에서 x행 y열의 값을 업데이트 할 때는,
(i-1)번째 연산에서 ( M[x-1][y], M[x][y-1], M[x][y] + r[i-x]*c[i-y] ) 중에서
최댓값으로 업데이트한다.
이렇게 총 N번 업데이트 하고 나서,
행렬 M의 최댓값을 구하면
그 값이 정답이다.

'Algorithm' 카테고리의 다른 글
최적의 행렬 곱셈 (12942번) - 프로그래머스 (Programmers) (0) | 2023.06.01 |
---|---|
문자열 폭발 (9935번) - 백준 (BOJ) (0) | 2023.05.30 |
1의 개수 세기 (9527번) - 백준 (BOJ) (0) | 2023.05.29 |
K번째 수 (1300번) - 백준 (BOJ) (0) | 2023.05.28 |
찾기 (1786번) - 백준 (BOJ) (0) | 2023.05.28 |