백준 15724 주지수 Python

🐸 문제 정보

15724번: 주지수

 

🤖 알고리즘

DP

 

⏱️ 풀이 시간

43.56m

 

📝 풀이

처음에 당연히 BFS라고 생각하고 푸는 바람에 어마어마하게 시간이 소요됐다.

이후에 DP + 누적합인 것을 알았음에도 풀이 방법이 바로 떠오르지 않았다.

사실 DP 문제들 중에서는 점화식을 찾기 쉬운 편의 문제였음에도 이렇게 시간이 오래 걸린다는 것은...

DP에 대한 연습이 부족하다는 것은 당연하고, DP는 연습해도 실전에서 못풀 가능성이 높다는게 무슨 소리인지 느낄 수 있었다.

 

누적합으로 (0,0)부터 특정 인덱스까지의 넓이를 구해줘야한다.

여기서 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + board[i][j] - dp[i - 1][j - 1] 이다.

쉽게 말해서 dp 리스트의 왼쪽 및 위쪽 값과, 기존 배열의 해당 인덱스 값을 합친 후, dp 리스트의 좌측 상단 값을 뺴라는 소리이다.

 

이렇게 완성된 dp 리스트에서 끝나는 지점의 값을 그냥 출력하면 안된다.

시작 지점의 인덱스를 (sx, sy)라고 하고, 종료 지점의 인덱스를 (ex, ey)라고 할 때

dp[ex][ey] - dp[sx - 1][ey] - dp[ex][sy - 1] + dp[sx - 1][sy - 1] 을 출력하면 된다.

 

 

55부터 끝까지인 경우, 남아있는 왼쪽과 위의 합계는 빼주어야한다.

하지만 그 과정에서 dp[sx - 1][sy - 1] 이 두 번 빠지게 되므로, 이 부분은 한 번 더해준다.

 

틀린 답

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start, end):
    q = deque([start])
    res = 0
    while q:
        px, py = q.popleft()
        for i in range(4):
            nx, ny = px + dx[i], py + dy[i]
            if (start[0] <= nx < end[0]) and (start[1] <= ny < end[1]) and (not visited[nx][ny]):
                visited[nx][ny] = True
                res += board[nx][ny]
                q.append((nx, ny))
    return res

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(int(input().rstrip())):
    idx = list(map(int, input().rstrip().split()))
    visited = [[False] * m for _ in range(n)]
    start = (idx[0] - 1, idx[1] - 1)
    end = (idx[2], idx[3])
    print(bfs(start, end))

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
board = [[0] * (m + 1)] + [[0] + list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [arr[:] for arr in board]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + board[i][j] - dp[i - 1][j - 1]

for _ in range(int(input().rstrip())):
    sx, sy, ex, ey = list(map(int, input().rstrip().split()))
    print(dp[ex][ey] - dp[sx - 1][ey] - dp[ex][sy - 1] + dp[sx - 1][sy - 1])