https://www.acmicpc.net/problem/1306
1306번: 달려라 홍준
첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째
www.acmicpc.net
세그먼트 트리 + 슬라이딩 윈도우 문제다.
풀이
세그먼트트리를 이용하여 구간별 최대값을 계산한다. 이후 홍준이의 위치를 포함한 앞 뒤 시야거리만큼의 범위로 구간별 최갯값을 출력하면 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| let NM = readLine()!.split(separator: " ").map{Int($0)!} | |
| let N = NM[0] | |
| let M = NM[1] | |
| var arr = readLine()!.split(separator: " ").map{Int($0)!} | |
| var tree = Array(repeating: 0, count: N*4) | |
| func make_tree(from:Int, to:Int, idx:Int)->Int{ | |
| if from == to{ | |
| tree[idx] = arr[from] | |
| return tree[idx] | |
| } | |
| let mid = (from+to)/2 | |
| let left = make_tree(from: from, to: mid, idx: idx*2) | |
| let right = make_tree(from: mid+1, to: to, idx: idx*2+1) | |
| tree[idx] = left<right ? right:left | |
| return tree[idx] | |
| } | |
| func read_tree(from:Int, to:Int, idx:Int, min:Int, max:Int) -> Int{ | |
| if to < min || max < from{ | |
| return 0 | |
| } | |
| if min <= from && to <= max{ | |
| return tree[idx] | |
| } | |
| let mid = (from+to)/2 | |
| let left = read_tree(from: from, to: mid, idx: idx*2, min: min, max: max) | |
| let right = read_tree(from: mid+1, to: to, idx: idx*2+1, min: min, max: max) | |
| return left<right ? right:left | |
| } | |
| make_tree(from: 0, to: N-1, idx: 1) | |
| var ans = [String]() | |
| for i in M-1..<N-M+1{ | |
| let l = i-(M-1) | |
| let r = i+(M-1) | |
| ans.append("\(read_tree(from: 0, to: N-1, idx: 1, min: l, max: r))") | |
| } | |
| print(ans.joined(separator: " ")) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [18436] 수열과 쿼리 37 (0) | 2023.02.21 |
|---|---|
| [14438] 수열과 쿼리 17 (0) | 2023.02.20 |
| [14428] 수열과 쿼리 16 (0) | 2023.02.17 |
| [11505] 구간 곱 구하기 (0) | 2023.02.16 |
| [2357] 최솟값과 최댓값 (0) | 2023.02.15 |