DP 응용문제(이코테) - 3

날짜 : 2022. . 

사용 언어 : python

 

문제

 

코드

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().split()) # n x m (행 x 열)
    total = list(map(int, sys.stdin.readline().split()))
    mine = []
    for i in range(n): mine.append(total[i:i + m])
    dp = [[0] * m for i in range(n)]
    for i in range(n): dp[i][0] = mine[i][0]

    for j in range(1, m): # 열
        for i in range(n): # 행
            # 왼쪽 위에서 오는 경우(i-1)
            if i == 0: left_up = 0
            else: left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우(i+1)
            if i == 0: left_down = 0
            else: left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우(i)
            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up, left, left_down)
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1]) # 마지막 열에 대해서 max 구하기
    print(result) # 출력

 

 

풀이

- 행과 열을 입력받고 먼저 dp의 첫번째 열에 대해서는 동일하게 입력받는다.(초기값이기 때문)

- 이후 반복문을 통해 다음 행으로 이동할 때 위에서 왔을 때, 같은 행에서 왔을 때, 아래에서 왔을 때를 분리하여 비교함으로써 진행시켜 나간다.

- 그렇기 때문에 먼저 열에 대하여 for문을 돌리고 내부에 행에 대하여 for문을 또 돌린다.

- 그 다음 위, 아래, 동일한 행에대한 값(left_up, left_down, left)들을 구한 후 비교한 후에 최댓값을 저장한다.

- 해당 for문을 탈출한 이후에는 마지막 열에 대하여 최댓값을 뽑아낸 후 값을 출력한다.

 

 

알게된 점

- 평소 1차원 리스트로만 문제를 풀다가 2차원 리스트로 문제를 푸니까 행인지 열인지 확실하게 기준이 안서기도 했고 꽤나 헷갈렸다.

- 코딩테스트 기출에도 굉장히 많이 나오는 주제이니만큼 문제를 자주 풀어보아야겠다.

 

 

참고 사이트

-