[백준 2167 / Python] 2차원 배열의 합

🧑🏻‍💻 문제링크

문제풀이

문제를 처음 보자마자 누적의 합을 구하기 위해서 2차원 배열상의 값들을 더하는 식으로 구현을 하였지만 PyP3로 하지 않는 이상 시간 초과로 문제를 틀려서 조금 고민했던 기억이 난다. 동적계획법을 사용해서 풀어야지 다른 이슈가 발생하지 않았고 코드도 좀 더 깔끔하게 작성할 수 있었다.

코드1(처음 풀었을 때)

# 배열의 크기 입력
N, M = map(int, input().split())
arr = [[0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    temp = list(map(int, input().split()))
    for j in range(1, M+1):
        arr[i][j] = temp[j-1]

# 부분의 개수 입력
K = int(input())

for _ in range(K):
    # (i, j) 에서 (x, y)
    i, j, x, y = map(int, input().split())
    result = 0

    # 계산
    for u in range(i, x+1):
        for w in range(j, y+1):
            result += arr[u][w]

    print(result)

코드2(동적계획법 사용)

# 배열의 크기 입력
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

# 부분의 개수 입력
K = int(input())
dp = [[0] * (M+1) for _ in range(N+1)]

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

for _ in range(K):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

결과