백준 #31910 이진수 격차

문제 링크

[31910 이진수 격차]

문제 설명

1또는 0이 적혀있는 격자무늬를 왼쪽 맨위에서 오른쪽 맨 아래로 이동하면서 문자열을 만들 때 문자열을 이진수로 해석한 값의 최대값을 구하는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp[0][0] = arr[0][0]
for i in range(1, N):
    dp[0][i] = dp[0][i - 1] * 2 + arr[0][i]
for j in range(1, N):
    dp[j][0] = dp[j - 1][0] * 2 + arr[j][0]

for i in range(1, N):
    for j in range(1, N):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) * 2 + arr[i][j]

print(dp[-1][-1])

풀이

이동 방향이 오른쪽 그리고 아래 두가지 방향으로만 가능하기때문에 DP가 제일 먼저 떠올랐다. 예전에 쇠파이프? 문제인가 그거는 오른쪽, 아래, 오른쪽아래(대각선) 총 세방향으로 움직이는 문제였는데 이건 두방향이라서 비교적 쉽게 풀 수 있었다!