Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- task cancellation
- task cancel
- uikit toast
- button configuration
- swift bottomsheet
- swift 점선
- swift concurrency
- rxdatasources
- reactorkit
- swift 백준
- swift dashed line
- custom ui
- Tuist
- RxSwift
- BFS
- scene delegate
- custom navigation bar
- traits
- DP
- domain data
- identifiable
- 타임라인 포맷팅
- coordinator
- SWIFT
- UIKit
- 버튼 피드백
- swift custom ui
- claen architecture
- swift navigationcontroller
- custombottomsheet
Archives
- Today
- Total
김경록의 앱 개발 여정
[Swift 백준] 11659 구간 합 구하기 4 본문

풀이 아이디어
누적 합 문제입니다.
평소 풀어보지 않은 유형이라 문제를 보고 생각나는 대로 풀었더니 시간 초과가 났습니다.
누적 합 문제의 기본 골자는 다음과 같습니다.
1. 각 원소의 누적 합을 미리 구해둔다.
2. 임의의 수 n부터 m까지의 누적합은 m까지의 누적합에서 n - 1까지의 누적합을 뺀 것과 같습니다.
공식의 숙지가 필요한 문제였습니다.
마치 dp 테이블을 미리 채워놓는것과 비슷한 느낌인 거 같아요
풀이
let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int($0)! }
let m = Int(readLine()!)!
// 인덱스 계산하기 쉽게 0을 채워줍니다
var prefix = [0] + Array(repeating: 0, count: n)
for i in 1...n {
//인덱스 주의
prefix[i] = prefix[i-1] + arr[i-1]
}
for _ in 0..<m {
let ij = readLine()!.split(separator: " ").map { Int($0)! }
let (i, j) = (ij[0], ij[1])
print(prefix[j] - prefix[i-1])
}
'Algorithm' 카테고리의 다른 글
[Swift 백준] 11660 구간 합 구하기 5 (0) | 2025.02.13 |
---|---|
[Swift 백준] 17390 이건 꼭 풀어야 해! (0) | 2025.02.12 |
[Swift 백준] 3184 양 (0) | 2025.02.07 |
[Swift 백준] 25192 인사성 밝은 곰곰이 (0) | 2025.02.06 |
[Swift 백준] 25304 영수증 (0) | 2025.02.06 |