[Python 3] BOJ - 5721 "사탕 줍기 대회"

 # 문제 링크

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

5721번: 사탕 줍기 대회

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다.

<그림 1. 열 단위의 다이나믹 프로그래밍>

 그림 1은 한 행을 기준으로 한 상태 공간 배열을 채우는 것을 나타낸다. 즉, 이 때의 상태 공간은 col[row][idx][status]이며 의미는 현재 row행을 기준으로 idx번째 열에서 status의 상태에 따라 얻을 수 있는 사탕의 최대 갯수이다. 문제의 조건에 따라 현재 열을 선택한다면 직전 열은 선택하면 안된다.

<그림 2. 현재 열을 선택하지 않는 경우>

 그림 2는 현재 1번째 열을 선택하지 않는 경우를 나타낸 것이다. 가능한 경우는 이전 열을 선택하여 문제의 조건에 의해 현재 열을 선택하고 싶어도 선택할 수 없는 경우거나, 이전 열을 선택하지 않지 않았음에도 그냥 현재 열을 선택하지 않는 경우 중 최대값이다.

<그림 3. 현재 열을 선택하는 경우>

 그림 3은 현재 1번째 열을 선택하는 경우이다. 가능한 경우는 이전 열을 선택하지 않아 문제의 조건에 의해 현재 열을 선택하는 경우밖에 없다. 따라서 이전 열을 선택하지 않은 경우에 현재 행에 놓여진 사탕의 갯수를 더해주면 된다. 즉, 점화식은 아래와 같다. $$\left\{\begin{matrix}
col[i][j][0] = max(col[i][j - 1][0], col[i][j - 1][1])
\\ 
col[i][j][1] = col[i][j - 1][0] + arr[i][j]
\end{matrix}\right.$$

<그림 4. 열을 기준으로 한 dp 배열>

 그림 4는 최종적인 dp배열을 나타낸 것이다. 그렇다면 현재 1 x 5짜리 배열에서 얻을 수 있는 사탕의 최대값은 무엇인가에 대한 대답을 할 수 있다. 이를 2차원으로 확장한다면, 현재 n행에서 뽑을 수 있는 사탕의 최대값이 된다

<그림 5. 행 단위의 다이나믹 프로그래밍>

 그림 5는 행 단위의 다이나믹 프로그래밍을 나타낸 그림이다. 역시, 문제 조건에 따라 현재 행을 고르지 않는 경우라면 이전 행을 고르거나 고르지 않는 경우 중 최대값이 된다. 반대로 현재 행을 고른다면 반드시 이전 행을 고르지 않아야 한다. 따라서 행을 기준으로 하는 점화식도 열의 점화식과 같음을 알 수 있다.

 이 때 val1을 1행을 뽑았을 때 얻을 수 있는 사탕의 갯수라고 하자. 그런데 그림 4의 논리에 의해 특정 행에 대해 얻을 수 있는 사탕의 최대값을 구해놓았다. 따라서, val1은 모든 status(0, 1)에 대해 col[1][0][status]부터 col[1][m][status]까지의 값 중 최대값이다. 또한 구해놓은 최대값은 문제의 조건에 따라 연속된 열을 선택한 경우가 없고, 행을 기준으로 할 때도 역시 연속된 행을 뽑지 않으므로 문제의 조건을 위배하지 않는다. 따라서 이 때 그림 5에서 채워진 dp값 중 최대값이 정답이 됨을 알 수 있다

 

# 코드

import sys

while True:
    # 입력부
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    # col : 열을 기준으로 한 다이나믹 프로그래밍 배열
    #       col[i][j][0] = 현재 i행을 기준으로 j열을 뽑지 않을 때 사탕의 최대값
    #       col[i][j][1] = 현재 i행을 기준으로 j열을 뽑을 때 사탕의 최대값
    col = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        col[i][0][1] = arr[i][0]
        
    # 점화식
    for i in range(n):
        for j in range(1, m):
            col[i][j][1] = col[i][j - 1][0] + arr[i][j]
            col[i][j][0] = max(col[i][j - 1][0], col[i][j - 1][1])
            
    # val : 현재 i번째 행에서 얻을 수 있는 사탕의 최대값
    val = [0] * n
    for i in range(n):
        temp = 0
        for j in range(m):
            temp = max(temp, col[i][j][0], col[i][j][1])
        val[i] = temp
        
    # row : 행을 기준으로 한 다이나믹 프로그래밍 배열
    #       row[i][0] = 현재 i번째 행을 뽑지 않을 때 얻는 사탕의 최대값
    #       row[i][1] = 현재 i번째 행을 뽑을 때 얻는 사탕의 최대값
    row = [[0] * 2 for _ in range(n)]
    row[0][1] = val[0]
    
    # 점화식
    for i in range(1, n):
        row[i][1] = row[i - 1][0] + val[i]
        row[i][0] = max(row[i - 1][0], row[i - 1][1])
        
    # 정답 출력
    print(max(row[n - 1][0], row[n - 1][1]))