1301. Number of Paths with Max Score(Hard)

 

Number of Paths with Max Score - LeetCode

문제 자체는 심플한 DP문제다. 어렸을 적 왕수학(?) 계산법으로 경로의 수를 구하는 방법이 결국엔 DP아니었나 싶다.

4트만에 Accepted가 되었는데... 문제를 풀면서 2개의 삽질이 있었다.

1개의 프로그래밍 언어적 잘못과 1개의 문제를 이해하지 못한 잘못이다.

 

1. 이중 리스트로 배열을 만드는데, 리스트 객체를 가지는 리스트를 만들어서 참조로 인한 오류가 있었다.

temp = list( ) 로 리스트 객체를 만들고 0을 append시킨 뒤 sum_score_board와 path_cnt_board에 넣어줬다. 당연히 sum_score_board와 path_cnt_board는 같은 리스트 객체를 가지고 있으니... 내가 예상했던 값을 각자 갖고 있을 수가 없었다...

 

2. 'and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7'

이 문항을 무시했었고. 또한 10^9 요게 문제였다. 10^9와 10**9는 다른다... 거듭제곱은 **로 해야한다.

^ 연산자는 xor 연산자이다... 10^9로 계산시키고 2번이나 제출했다...

 

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        y_size = len(board)
        x_size = len(board[0])
        sum_score_board = list()
        path_cnt_board = list()
        for y in range(y_size):
            sum_score_board.append(list())
            path_cnt_board.append(list())
            for x in range(x_size):
                sum_score_board[y].append(0)
                path_cnt_board[y].append(0)
        
        x = x_size - 1
        y = y_size - 1
        sum_score_board[y][x] = 0
        path_cnt_board[y][x] = 1
        for y in range(y_size-1,-1,-1):
            for x in range(x_size-1,-1,-1):
                # print("Current : [{},{}] - {}".format(y,x,board[y][x]))
                # print("Max SUM : {}".format(sum_score_board[y][x]))
                # print("Path Cnt : {}".format(path_cnt_board[y][x]))
   
                if board[y][x] == 'X' or board[y][x] == 'S':
                    if board[y][x] == 'X':
                        sum_score_board[y][x] = -1
                    continue 
                max_sum = 0
                if board[y][x] != 'E':
                    max_sum = int(board[y][x])
                max_sum_right = max_sum
                max_sum_down = max_sum
                max_sum_downright = max_sum
                #RIGHT
                if x != x_size-1:
                    max_sum_right += sum_score_board[y][x+1]
                #DOWN
                if y != y_size-1:
                    max_sum_down += sum_score_board[y+1][x]
                    #DOWN_RIGHT
                    if x != x_size-1:
                        max_sum_downright += sum_score_board[y+1][x+1]

                max_sum = max(max_sum_right, max_sum_down, max_sum_downright)
                sum_score_board[y][x] = max_sum
                path_cnt_board[y][x] = 0
                if x != x_size-1 and max_sum == max_sum_right:
                    path_cnt_board[y][x] += path_cnt_board[y][x+1]
                    # print("RIGHT : {}".format(max_sum_right))
                if y != y_size-1 and max_sum == max_sum_down:
                    path_cnt_board[y][x] += path_cnt_board[y+1][x]
                    # print("DOWN : {}".format(max_sum_down))
                if (y != y_size-1 and x != x_size-1) and max_sum == max_sum_downright:
                    path_cnt_board[y][x] += path_cnt_board[y+1][x+1]
                    # print("DOWNRIGHT : {}".format(max_sum_downright))
                # print("Current SUM : {} - CNT : {}".format(sum_score_board[y][x], path_cnt_board[y][x]))
                path_cnt_board[y][x] = path_cnt_board[y][x] % (10**9+7) # <- 이것 때문에 엄청 헤맸음...
        if path_cnt_board[0][0] == 0:
            sum_score_board[0][0] = 0
        return [sum_score_board[0][0], path_cnt_board[0][0]]