본문 바로가기

Algorithm

숫자 박스 (1983번) - 백준 (BOJ)

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을 모두 제거해보면 아래와 같은 수열이 된다.

 

문제 예제 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의 최댓값을 구하면

그 값이 정답이다.

 

최댓값을 찾는 과정