728x90
https://www.acmicpc.net/problem/11659
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๋์ ํฉ์ ์ฒ์ ์ ํ๋ค.
๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๊ฐ์ ๊ณ์ฐํด์ ์ ์ฅํด์ ๊บผ๋ด์ ์ฌ์ฉํ๋ฉด ๋ ๊ฒ ๊ฐ๋ค๋ ์๊ฐ์ ๋ค์๋๋ฐ, ์ ํํ ํด๊ฒฐ๋ฐฉ๋ฒ์ด ๋์ ํฉ!์ธ์ง๋ ๋ชฐ๋๋ค..!
๋์ ํฉ์ ๋ํด ์์๋ณด์!
๋์ ํฉ
ํน์ ๊ตฌ๊ฐ์ ํฉ์ ์ฐพ๋๋ฐ ์ ์ฉํ ์๊ณ ๋ฆฌ์ฆ
๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ์ ์ฐ์๋ ์์๋ค์ ํฉ์ ๋น ๋ฅด๊ฒ ๊ณ์ฐํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๋ฐฐ์ด๊ณผ ๊ฐ์ ์ํ์ค ๋ฐ์ดํฐ์์ ์ผ๋ถ ๊ตฌ๊ฐ์ ํฉ์ ์ฐพ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฒด ๋ฐฐ์ด์ ๋ฐ๋ณตํด์ ๋ง์ ์ ์ํํ๋ ๋ฐฉ์๋ณด๋ค ๋น ๋ฅธ ๊ณ์ฐ์ ๊ฐ๋ฅํ๊ฒ ํฉ๋๋ค.
๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ ์๋ ๋ฐฉ์
- ๋์ ๋ฐฐ์ด ์์ฑ: ์๋์ ๋ฐฐ์ด๊ณผ ๊ฐ์ ๊ธธ์ด๋ฅผ ๊ฐ๋ ๋ฐฐ์ด์ ๋ง๋ญ๋๋ค. ์ด ๋ฐฐ์ด์ ๊ฐ ์ธ๋ฑ์ค๋ ์๋ ๋ฐฐ์ด์ ์ธ๋ฑ์ค๊น์ง์ ํฉ์ ์ ์ฅํฉ๋๋ค.
- ๋์ ๋ฐฐ์ด ๊ฐ ๊ฐฑ์ : ๋์ ๋ฐฐ์ด์ ๊ตฌ์ฑํ ๋, ๊ฐ ์์๋ ํด๋น ์ธ๋ฑ์ค๊น์ง์ ํฉ์ ๋ํ๋ ๋๋ค. ์๋ฅผ ๋ค์ด, ๋์ ๋ฐฐ์ด์ i๋ฒ์งธ ํญ๋ชฉ์ ์๋ ๋ฐฐ์ด์ 0๋ฒ์งธ๋ถํฐ i๋ฒ์งธ๊น์ง์ ํฉ์ ๋ํ๋ ๋๋ค.
- ํน์ ๊ตฌ๊ฐ ํฉ ๊ณ์ฐ: ๊ตฌ๊ฐ[i, j]์ ํฉ์ ๋์ ํฉ[j]์์ ๋์ ํฉ[i-1]์ ๋นผ๋ฉด ์ฝ๊ฒ ๊ตฌํ ์ ์์ต๋๋ค. ์ด๋ก์จ, ๋ฐฐ์ด์ ํน์ ๊ตฌ๊ฐ์ ํฉ์ ๊ณ์ฐํ๋ ๋ฐ ์๊ฐ ๋ณต์ก๋ O(1)์ ๊ตฌํ ์ ์์ต๋๋ค.
func calculatePrefixSum(_ arr: [Int]) -> [Int] {
var prefixSum = [Int](repeating: 0, count: arr.count)
// ์ฒซ ๋ฒ์งธ ์์๋ ์๊ธฐ ์์ ์ด๋ฏ๋ก ์๋ ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ๊ฐ์ผ๋ก ์ด๊ธฐํ
prefixSum[0] = arr[0]
// ๋์ ํฉ ๋ฐฐ์ด ๊ตฌ์ฑ
for i in 1..<arr.count {
prefixSum[i] = prefixSum[i - 1] + arr[i]
}
return prefixSum
}
func cal(_ start: Int, _ end: Int) -> Int {
if start == end { return arr[start] }
if start == 0 { return prefixSumArray[end] }
return prefixSumArray[end] - prefixSumArray[start-1]
}
// ์์ ๋ฐฐ์ด
let arr = [3, 1, 7, 5, 2, 4]
// ๋์ ํฉ ๊ณ์ฐ
let prefixSumArray = calculatePrefixSum(arr)
print("๋์ ํฉ ๋ฐฐ์ด: \(prefixSumArray)")
// ๊ตฌ๊ฐ ์ธ๋ฑ์ค[2, 4]์ ํฉ
let result = cal(2, 4) // ์ธ๋ฑ์ค์ ์ ์
728x90
'๐ Algorithm > ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] 03. ์์ด๊ณผ ์กฐํฉ, ๊ทธ๋ฆฌ๊ณ ์ฌ๊ท with Swift (1) | 2024.02.06 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] 02. BFS์ DFS ์๊ณ ๋ฆฌ์ฆ์ ๋ผ๋ with Swift (1) | 2023.12.28 |