[백준/BOJ] silver2 - 31910번 이진수 격차 (Python)

▶31910 - 이진수 격차

백준 로고

 

▶문제

각 칸에 0 또는 1이 적혀 있는 N×N 격자가 있다. 인선이는 1행 1열에서 출발해 N행 N열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 1행 1열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.

 N행 N열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 M을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 M = 13이다. 인선이가 계산하게 될 M의 최댓값을 구하시오.

 

▶입력

첫째 줄에 격자의 크기를 의미하는 정수 N이 주어진다. (2 ≤ N ≤ 30)

둘째 줄부터 N개의 줄에 걸쳐 한 줄에 N개의 정수가 공백으로 구분되어 주어진다. 이 정수는 반드시 0 또는 1이다. (i+1) 번째 줄에 주어진 j번째 수는 i행 j열에 적힌 격자의 칸에 적힌 수를 의미한다.

 

▶출력

M의 최댓값을 출력한다. 정답이 32비트 정수 범위를 넘을 수 있음에 주의하시오.

728x90

▶풀이

일반적인 dp 문제랑 거의 동일한 문제이다.

단순히 덧셈만 하는 것이 아닌, 중간에 2를 곱하면서 더해가는 것이 핵심이다.

그 외에는 특별한 것이 없는 문제라 쉽게 풀 수 있다.

n = int(input())
arr = []
dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    arr.append(list(map(int, input().split())))

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