(Elice / 시뮬레이션 / Python)엉망진창 다과회

엉망진창 다과회

모자장수와 3월의 토끼가 다과회 테이블에 배치할 차의 위치에 대해서 몇 시간째 싸우고 있습니다.
모자장수는 홍차를 좋아하여 홍차를 더 많이 테이블 위에 올리고 싶었고 토끼는 케이크를 좋아해서 케이크를 더 많이 테이블에 올려 두고 싶었기 때문인데요.

방금, 다과회에 도착한 엘리스는 싸움을 중재하기 위해 일부 칸에 있는 음식을 전부 제거하고, 그 칸을 경계선으로 두가지 영역을 나누는 방법을 떠올렸습니다!!

테이블의 크기는 직사각형이고, H x W 개의 칸으로 나누어져 있습니다. 모든 칸에는 홍차(Black Tea) 또는 케이크(Cake)가 위치해있습니다. 경계선은 가장 왼쪽 위칸에서 출발하며, 한 칸 아래, 오른쪽, 오른쪽 아래 대각선으로 이동할 수 있다. 선은 오른쪽 아래칸에 도착할 때까지 이동합니다.

모자장수의 홍차(Black Tea)는 선이 지나간 길의 아래쪽에 칸을 얻게 되고, 토끼의 케이크(Cake)는 위쪽의 칸을 얻게 됩니다. 따라서, 칸을 하나도 받지 못하는 경우가 생길 수도 있습니다.
엘리스는 풍족한 다과회를 위해 아래 쪽에 있는 모자장수의 홍차와 위 쪽에 있는 토끼의 케이크의 합을 크게 만들려고 합니다.

엘리스를 위해 가능한 합 중 가장 큰 합을 구하는 프로그램을 작성하세요.

입력 예시

4 3
C3 B2 C6
B5 C1 C4
B2 B4 B1
C1 C3 B3

출력 예시

21

 

 

          입력                                                                                         출력

입력 

• 첫째 줄에 테이블의 크기 Heigh와 Width가 주어집니다. (2 ≤ Width,Height≤ 1500)
• 둘째 줄부터 각 줄에는 각 칸에 배치되어 있는 차나 케이크의 개수가 주어집니다. 홍차는 B, 케이크는 C이고, 각 칸에 배치 되어 있는 개수는 1보다 크거나 같고, 99보다 작거나 같습니다.

 

출력

• 가능한 합 중 가장 큰 것을 출력해주세요.

소스 코드

h,w = map(int,input().split())

table = []

b = [[0] * (w+2) for i in range(h+1)]
c = [[0] * (w+2) for i in range(h+1)]
dp = [[0] * (w+2) for i in range(h+1)]


for i in range(h):
    table.append(input().split())

for i in range(h):
    for j in range(w):
        if (table[i][j][:1] == "B"):
            b[i+1][j+1] += int(table[i][j][1:])
        else:
            c[i+1][j+1] += int(table[i][j][1:])

for i in range(1, h+1):
    for j in range(1, w+1):
        b[i][j] += b[i][j-1]
        c[i][w-j+1] += c[i][w-j+2] 

for i in range(1, h+1):
    for j in range(1, w+1):
        if (i == 1 or j == 1):
            dp[i][j] = dp[i-1][j] + c[i][j+1]
            continue
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + b[i][j-1] + c[i][j+1]
        dp[i][j] = max(dp[i][j], dp[i][j-1] - c[i][j] + c[i][j+1])

print(dp[h][w])