[엘리스] 엉망진창 다과회

엉망진창 다과회

모자장수와 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보다 작거나 같습니다.

출력

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

풀이 (오답)

• DFS를 이용한 접근

• 대각선인 경우는 0을 삽입, 0의 왼쪽에 B가 나오면 cnt를 더해주고 마찬가지로 0의 오른쪽에 C가 나오면 cnt를 더해줌

• 하지만, 시간초과 발생

from heapq import heappush, heappop 


def dfs(myMap, y, x): 

    result = [] 
    dx = [1, 1, 0]
    dy = [0, 1, 1]

    if (y == len(myMap) - 1) & (x == len(myMap[0]) - 1):
        cnt = 0
        for i in range(len(myMap)):
            flag = True
            for j in range(len(myMap[0])):
                if myMap[i][j] == 0:
                    flag = False
                    continue
                else:
                    if (flag == True) & (myMap[i][j][0] == 'B'):
                        cnt += int(myMap[i][j][1:])
                    elif (flag == False) & (myMap[i][j][0] == 'C'):
                        cnt += int(myMap[i][j][1:])
                    else:
                        continue
        result.append(cnt)
        # print(myMap, cnt)
        return result 
    else:
        for i in range(len(dx)):
            if ((y + dy[i]) <= len(myMap) - 1) & ((x + dx[i]) <= len(myMap[0]) - 1):
                value = myMap[y + dy[i]][x + dx[i]]
                myMap[y + dy[i]][x + dx[i]] = 0
                result += dfs(myMap, y + dy[i], x + dx[i])
                myMap[y + dy[i]][x + dx[i]] = value 
            else:
                continue 

    return result 



A = list(map(int, input().split()))
M = A[0]
N = A[1] 
myMap = [[0 for c in range(N)] for c in range(M)]

for i in range(A[0]):
    A = list(map(str, input().split()))
    myMap[i] = A


myMap[0][0] = 0
sol = dfs(myMap, 0, 0)
print(max(sol))

모범 답안

• DP를 이용한 접근

  • DP[i][j]의 경우 왼쪽, 왼쪽 대각선 위, 위 3가지 경우 중 하나가 최대가 됨

    • 왼쪽 대각선 위, 바로 위의 경우 : max(dp[i-1][j-1], dp[i-1][j]) + b[i][j-1] + c[i][j+1]

    • 왼쪽의 경우 : max(dp[i][j], dp[i][j-1] - c[i][j] + c[i][j+1])

  • b, c : 홍차와 케이크의 누적합

    • 홍차(b)는 순서대로 누적합

    • 케이크(c)는 역순으로 누적합

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])

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn