실버 I

💡문제 분석 요약

다이내믹 프로그래밍

💡알고리즘 설계

구간합을 dp에 저장한다.

주어진 범위를 구하기 위해, 포함되지 않는 공간을 빼서 구한다.

참고한 블로그

https://chanhuiseok.github.io/posts/baek-19/

💡코드

import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())

arr = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (N+1) for _ in range (N+1)]

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

for _ in range (M) :
    x1, y1, x2, y2 = map(int, input().split())

    ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

    print(ans)

💡시간복잡도

💡 틀린 이유

문제를 아예 이해하지 못했다.

💡 다른 코드

0으로 초기화한 dp, array의 첫 값을 가진 list

list는 증가하는 부분 수열을 나타낸다.

array 를 돌면서, list 마지막 값과 arry값을 비교한다. 만약, array값이 더 크다면, list에 array값을 더해준다.

array값이 더 작다면(즉, array[i]가 수열에 들어갈 수 없으면), 만든 수열을 돌면서 array[i]보다 큰 값을 찾고, 거기에 수열 array 값을 넣어준다.

더 작은 값을 넣어야 길어지기 때문에 큰 값을 그나마 작은 array현재 값으로 변경하고, 그 뒤에 받을 값의 범위를 확장하기 위함이다. ← 이것을 biscet으로 구현하면 이진탐색을 쓰기에 더 빠르고 쉽게 구할 수 있다.

그리고 list의 길이를 print()한다.

for i in range(x):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])#대
        dp[idx] = arr[i]

💡 기억할정보

문제를 제대로 이해하고 나서 풀자

1160번 구간 합 구하기 5

DP