https://www.acmicpc.net/problem/3770
세그먼트 트리문제다. [7578] 공장 문제와 같은 풀이로 접근가능하다.
풀이
[7578] 공장 문제와 달리 유의할 점은 입력되는 간선의 정렬이 필요하다는 점이다.
출발지 기준 오름차순, 출발지가 같다면 도착지기준 오름차순으로 고속도로 정보를 정렬한 뒤, 매 순간 도착도시 다음번호 ~ 마지막 도착도시 구간의 건설된 고속도로의 개수 총합을 출력하면 된다.
입력 예제를 기준으로 시나리오를 그려보면 다음과 같다.
좌측의 N개의 도시, 우측의 M개의 도시와 정렬된 간선 그리고 구간 합 세그먼트 트리를 생성한다.
1번 도시와 4번 도시를 연결, 4번은 가장 마지막 도시이므로 구간합 조회 시 범위를 넘어가게 되어 0을 반환하게 된다.
다음 탐색을 위해 4번 노드에 1 추가.
2번 도시와 3번 도시 연결, 이때 3번 도시 이후의 구간 즉 4~4번 구간의 고속도로의 개수 1을 정답에 추가한다.
이후 3번 노드에 1 추가.
3번 도시와 1번 도시 연결, 2번 도시부터 4번 도시 구간의 고속도로의 수를 조회한다. 고속도로의 개수 2가 반환된다.
이후 1번 노드에 1 추가.
마지막으로 3번 도시와 2번 도시 연결, 3번 도시와 4번 도시 구간합을 조회. 정답에 해당 구간값 2를 추가한다.
2번 노드에 1 추가.
정답 코드
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 | |
| //by rhyno | |
| final class FileIO { | |
| private let buffer:[UInt8] | |
| private var index: Int = 0 | |
| init(fileHandle: FileHandle = FileHandle.standardInput) { | |
| buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지 | |
| } | |
| @inline(__always) private func read() -> UInt8 { | |
| defer { index += 1 } | |
| return buffer[index] | |
| } | |
| @inline(__always) func readInt() -> Int { | |
| var sum = 0 | |
| var now = read() | |
| var isPositive = true | |
| while now == 10 | |
| || now == 32 { now = read() } // 공백과 줄바꿈 무시 | |
| if now == 45 { isPositive.toggle(); now = read() } // 음수 처리 | |
| while now >= 48, now <= 57 { | |
| sum = sum * 10 + Int(now-48) | |
| now = read() | |
| } | |
| return sum * (isPositive ? 1:-1) | |
| } | |
| } | |
| let io = FileIO() | |
| let T = io.readInt() | |
| var ans = [String]() | |
| for tc in 1...T{ | |
| let N = io.readInt() | |
| let M = io.readInt() | |
| let K = io.readInt() | |
| var result = 0 | |
| var tree = Array(repeating: 0, count: M*4) | |
| var edges = [(u:Int,v:Int)]() | |
| func update_tree(start:Int, end:Int, node:Int, idx:Int){ | |
| if idx < start || end < idx{ return } | |
| tree[node] += 1 | |
| if start == end{ return } | |
| let mid = (start+end)/2 | |
| update_tree(start: start, end: mid, node: node*2, idx: idx) | |
| update_tree(start: mid+1, end: end, node: node*2+1, idx: idx) | |
| } | |
| func read_tree(start:Int, end:Int, node:Int, from:Int, to:Int) -> Int{ | |
| if end<from || to<start || to<from{ return 0 } | |
| if from<=start && end<=to{ return tree[node] } | |
| let mid = (start+end)/2 | |
| let left = read_tree(start: start, end: mid, node: node*2, from: from, to: to) | |
| let right = read_tree(start: mid+1, end: end, node: node*2+1, from: from, to: to) | |
| return left+right | |
| } | |
| for _ in 0..<K{ | |
| let u = io.readInt()-1 | |
| let v = io.readInt()-1 | |
| edges.append((u,v)) | |
| } | |
| edges.sort(by: { | |
| if $0.u == $1.u{ | |
| return $0.v < $1.v | |
| }else{ | |
| return $0.u < $1.u | |
| } | |
| }) | |
| for edge in edges{ | |
| let v = edge.v | |
| result += read_tree(start: 0, end: M-1, node: 1, from: v+1, to: M-1) | |
| update_tree(start: 0, end: M-1, node: 1, idx: v) | |
| } | |
| ans.append("Test case \(tc): \(result)") | |
| } | |
| print(ans.joined(separator: "\n")) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [13334] 철로 (0) | 2023.03.26 |
|---|---|
| [3895] 그리고 하나가 남았다 (0) | 2023.03.24 |
| [3653] 영화 수집 (0) | 2023.03.12 |
| [7578] 공장 (0) | 2023.03.11 |
| [1280] 나무 심기 (1) | 2023.03.09 |
