[Swift Algorithm] 구간 합 구하기 4 BOJ #11659

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

입출력 예제

입력

5 3
5 4 3 2 1
1 3
2 4
5 5

출력

12
9
1

 

내 문제 풀이

let info = readLine()!.split(separator: " ").map({Int(String($0))!})
let nums = readLine()!.split(separator: " ").map({Int(String($0))!})
var sum = [0, nums[0]]

for i in 2...info[0] {
    sum.append(nums[i-1] + sum[i-1])
}

for _ in 0..<info[1] {
    let section = readLine()!.split(separator: " ").map({Int(String($0))!})
    print(sum[section[1]] - sum[section[0]-1])
}

👉 dp 문제로, 메모이제이션 방식을 잘 활용해주는게 포인트!

처음 이 문제를 접했을 때는, 그냥 반복으로 더해주면되는거 아닌가 왜 dp지ㅜ 했는데

그렇게 하면 시간초과!! 알고보니 역시나 메모이제이션으로 저장해놓고 값을 활용하는 방식이었다.

• 첫 for문으로 우선 1부터 끝까지 누적 값을 넣는 배열을 완성해주었다.
• 그리고 두 번째 for문에서는 구간을 받아오고, 바로 그에 맞는 연산 결과를 출력해주었다.
  (예를 들어 1부터 3까지를 구하고 싶다면, sum[3] - sum[0]을 해주면 알맞은 결과를 구할 수 있다.)

 

💡 피드백

• 역시나 DP문제의 핵심은 중복을 피해야 한다는 점인 것 같다.
  DP문제에서 시간초과가 발생한다면, 중복적인 연산이 계속되지는 않는지 확인해볼것!

 

---

문제

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