Baekjoon 문제 풀기 (2167번 : 2차원 배열의 합) Python

2167번 : 2차원 배열의 합

1. 문제읽기

---

누적합 계산하기

또 문제부터 잘못 읽었다.^^…
진짜 앞으로는 30분 칼같이 재서 안풀리면 바로 답을 봐야겠다.
(i, j) 위치부터 (x, y) 위치까지 저장되어 있는 수의 합을 잘못이해해서 연달아 있는 수라고 생각했는데, 그러면 (1,3)부터 (2,3)까지의 합이 36이 이상하다고 생각하긴 했다..

어쨌든 이 문제는 누적합!! 으로 풀면 되고, 일반적인 for문 반복 방법과 dp 알고리즘 두가지 방법이 있었다.

2. 제출 코드

---

시간초과로 틀린 코드.
심지어 문제 자체도 이해를 잘못해서 (1,1)부터 (2,3)이면, 직사각형의 범위만큼이라고 생각한 것이 아니라 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) 이렇게 쭉 이어지는 값을 더하는 것이라고 생각했다.
어쨌든 예제는 맞았는데 시간초과가 아니었어도 결국엔 히든 테스트케이스에서 틀렸을 것이다.

그래도 뭔가 0값으로 초기화 된 배열을 만든 것과 for문을 사용하여 값을 입력받은 것까지는 비슷해서 기분이 완전 다운되지는 않았다!

n, m = map(int, input().split())

arr = [0]*(n+1)  # [0, 0, 0]

# 0행 0열 만들기
arr[0] = [0 for _ in range(m+1)]
# 값 넣어주기
for i in range(1, n+1):  # 2번 반복(1, 2)
    ele_list = list((map(int, input().split())))  # 입력값 리스트 [1, 2, 4]
    arr[i] = [0] + ele_list

# arr = [[0,0,0,0],[0,1,2,4],[0,8,16,32]]

k = int(input())  # k=3

for _ in range(k):  # 3번 반복
    total = 0
    i, j, x, y = map(int, input().split())  # i=1 j=1 x=2 y=3
    if i == x and j != y:  # x값만 같을 때
        for j in range(y+1):
            total += arr[i][j]
    elif i != x and j == y:  # y값만 같을 때
        for i in range(x+1):
            total += arr[i][j]
    elif i == x and j == y:  # 두 값이 모두 같을 때
        total = arr[i][j]
    else:  # 모두 다른 값일 때
        for i in range(x+1):
            for j in range(y+1):
                total += arr[i][j]
    print(total)

3. 공부할 것

---

for문을 두번 중첩하는 문제를 예상하고 문제를 낸 것 같진 않은데, 분류에 dp가 없는 것을 보니 아리송하다.
검색을 좀 해보니 for문 합을 누적시키는 방법으로 문제를 풀면 pypy3으로 내야 겨우 통과할 수 있을 거라고해서 dp 방법으로 푸는 게 더 나아보인다.

이 문제에 대해 이해하기 쉽게 정리한 블로그 글이 있어서 참고하였다.