[Algorithm] 11659. 구간 합 구하기 4

11659: 구간 합 구하기 4 (DP)

https://www.acmicpc.net/problem/11659

• 문제 티어 : S3
• 풀이 여부 : Falied
• 소요 시간 : 00:13:33

정답 코드

# DP : O(N + M)
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = [0] + list(map(int, input().rstrip().split()))

# DP 테이블 초기화
dp = [0] * (N+1) # 1~N번째 원소 저장
for i in range(1, N+1):
  dp[i] = dp[i-1] + arr[i] # 첫번째 원소부터 i번째 원소까지의 누적합

# 누적합 구하기
for _ in range(M):
  L, R = map(int, input().rstrip().split())
  #print(dp, R, ':', dp[R], L-1, ':', dp[L-1], dp[R] - dp[L-1])
  print(dp[R] - dp[L-1])

접근 방식

• DP 테이블을 1~N까지 반복해 첫번째 원소부터 i번째 원소 누적합으로 초기화
• L부터 R까지의 누적합을 구하는 접근방법을 기존에는 투포인터처럼 접근해야겠다고 생각 → R까지의 누적합에서 L-1까지의 누적합을 빼주면 되는 문제!
  

잘못된 접근 방식(+ 코드)

분명 누적합을 구하는 부분에서 있어서 DP를 사용해야 하는 문제라고 생각했지만,

base case와 점화식을 못세우겠어서 다짜고짜 완전탐색으로 풀었다.

그 결과 채점 40%만에 시간초과 가 났다.

# 완탐 : O(MN) ->  O(10^10)
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = [0] + list(map(int, input().rstrip().split()))
task = [list(map(int, input().rstrip().split())) for _ in range(M)]
memo = {i:arr[i] for i in range(len(arr))}

for i in range(len(task)): 
  print(sum(arr[task[i][0]:task[i][1]+1])) 

배운점 또는 느낀점

시간복잡도 계산해보고 DP로 풀어야한다고 생각되는 문제는 꼭 관계 찾기

1. 계산의 중복 여부
2. 앞 결과가 미치는 영향 고려