[Python/BOJ] 1983. 숫자 박스

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

1983번: 숫자 박스

문제

그림과 같이 숫자 박스는 위와 아래의 두 행과 N개의 열로 나누어져 있다. 따라서 숫자 박스는 전체 2N개의 칸으로 이루어져 있고, 각 칸에는 0이 아닌 -10 이상 10 이하의 정수가 적힌 숫자판이 들어갈 수 있다. 아래 그림은 N=7 인 경우 어떤 숫자 박스의 상태를 보여주고 있다. 빈칸은 숫자판이 들어있지 않은 칸을 나타내며, 위와 아래의 행에 들어있는 숫자판의 개수는 같지 않을 수도 있다.

-3	-1	-2		5	-1
	-3	2	4		5	-2

숫자 박스의 "값"은 각 열의 위와 아래에 있는 두 숫자들의 곱을 모두 더한 값으로 정의된다. 빈칸은 0으로 계산한다. 예를 들면, 위 그림의 숫자 박스의 값은 (-3)×0 + (-1)×(-3) + (-2)×2 + 0×4 + 5×0 + (-1)×5 + 0×(-2) = -6 이다. 각 행에 주어진 숫자판들에 대해 그 순서를 유지하면서 좌우로 움직이면 다른 숫자 박스의 “값”을 얻을 수 있다. 위의 예에서 윗 행에 있는 5와 -1을 오른쪽으로 각각 한 칸씩 옮기고, 아래 행의 -3을 왼쪽으로 한 칸, 2와 4를 오른쪽으로 각각 한 칸씩 옮기면 그 결과 숫자 박스는 다음과 같다.

-3	-1	-2			5	-1
-3			2	4	5	-2

이 숫자 박스의 “값”은 9 + 25 + 2 = 36이 된다. 주어진 숫자 박스의 위와 아래의 행에 놓인 숫자판들을 그 순서는 유지하면서 위의 조건을 만족하도록 움직여서 얻을 수 있는 숫자 박스의 최댓값을 구하는 프로그램을 작성하시오. 숫자판들은 좌우 빈칸으로만 움직일 수 있으며, 건너뛰는 형태로 다른 숫자판과 그 위치가 교환될 수는 없다. 다시 말하면, 빈칸을 제외하면 각 행의 숫자판들의 순서는 항상 그대로 유지되어야 한다.

입력

첫 줄에는 숫자 박스의 열의 수를 나타내는 정수 N(1 ≤ N ≤ 400)이 주어진다. 그 다음 두 줄에는 각각 숫자 박스의 위와 아래의 행에 놓인 초기 숫자판들의 숫자가 하나 이상의 공백을 두고 나타나는데, 숫자판이 없는 빈칸은 0으로 표시된다. 단, 숫자판의 숫자는 모두 -10 이상 10 이하의 0이 아닌 정수이다.

출력

입력으로 주어진 숫자 박스의 각 행의 숫자판들을 가로로 이동시켜 얻을 수 있는 숫자 박스의 최댓값을 첫 번째 줄에 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

n = int(input())
array1, array2 = list(map(int, input().split())), list(map(int, input().split()))
row1, row2 = [], []
row1_zero = row2_zero = 0

# 1. 1행과 2행의 0의 갯수 추출
# 2. 0이 제거된 1행과 2행 추출
for i in range(n) :
    if array1[i] == 0 : row1_zero += 1
    else : row1.append(array1[i])

    if array2[i] == 0 : row2_zero += 1
    else : row2.append(array2[i])
# 3. 한 행이 모두 0으로 구성되어 있는 경우 0 출력
if row1_zero == n or row2_zero == n : print(0)
else :
    # 4. dp 생성
    dp = [[[0 for _ in range(row2_zero + 1)] for _ in range(row1_zero + 1)] for _ in range(n)]
    # 5. 초기값 설정
    dp[0][0][0] = row1[0] * row2[0]
    # 6.
    for i in range(1, n) :
        for x in range(row1_zero + 1) :
            if i-x < 0 or i-x >= len(row1) : continue
            for y in range(row2_zero + 1) :
                if i-y < 0 or i-y >= len(row2): continue
                # 6-1. 점화식에 따라 처리
                dp[i][x][y] = dp[i-1][x][y] + row1[i-x] * row2[i-y]
                if x-1 >= 0 : dp[i][x][y] = max(dp[i][x][y], dp[i-1][x-1][y])
                if y-1 >= 0 : dp[i][x][y] = max(dp[i][x][y], dp[i-1][x][y-1])
    # 7. 결과 출력
    print(dp[-1][-1][-1])