[BOJ 24527] 백준 24527번 - 이상한 나라의 갈톤보드
| 2022 성균관대학교 프로그래밍 경진대회 Open Contest 풀이 | ||
|---|---|---|
| A | [BOJ 24523] 내 뒤에 나와 다른 수 | |
| B | [BOJ 24524] 아름다운 문자열 | |
| C | [BOJ 24525] SKK 문자열 | |
| D | [BOJ 24526] 전화 돌리기 | |
| E | [BOJ 24527] 이상한 나라의 갈톤보드 |
1. 문제
$24527$. 이상한 나라의 갈톤보드 (2022 성균관대학교 프로그래밍 경진대회 Open Contest E번)
백준 24527번 - 이상한 나라의 갈톤보드 (https://www.acmicpc.net/problem/24527)
2. 풀이
시작지점의 번호로부터 그 시작지점의 높이와 해당 높이에서 몇 번째 숫자인지의 두 가지 정보를 알아낼 수 있다면, 구슬의 도착지점의 범위를 알아낼 수 있다.
높이가 $h(1\leq h\leq H)$이면, 해당 높이의 첫 번째 숫자는 $\frac{(h-1)\times h}{2}+1$이고, 해당 높이의 마지막 숫자는 $\frac{(h)\times (h+1)}{2}$이다. 이를 토대로 이분탐색을 통해 시작지점의 번호로 $h$를 찾을 수 있다.
$h$를 찾게 되면, $h$와 시작지점의 번호의 계산으로 해당 높이에서 몇 번째 숫자인지도 구할 수 있다.
기댓값 = (사건의 값) * (그 사건이 벌어질 확률) 이다. 따라서 도착지점의 구슬 개수 기댓값을 구한다는 것은, 시작지점에서 출발한 임의 개수의 구슬의 도착지점 범위가 $A\sim B$라고 가정할 경우, $A$부터 $B$까지의 각각의 기댓값이 $(구슬\,개수) \times (1/(범위의\,길이:\, B-A+1))$만큼 증가한다는 의미이다.
이를 통해 $Q$개의 쿼리만큼 구슬을 떨어뜨리면, 모든 지점에서의 각각의 기댓값이 완성된다.
그런데, $Q\leq 100,000$에 도착지점이 될 수 있는 범위는 $1\sim H+1(H+1\leq 100,001)$이다. 따라서 일일이 더하는 작업으로는 시간초과 발생이 예상된다. 게다가 도착지점$[a, b]$에 떨어지는 $R(R\leq 100,000)$개의 쿼리를 처리하기 위해서는 $a$부터 $b$까지의 기댓값을 더하는 작업이 필요한데 그 또한 시간초과가 예상된다.
이 두 가지 작업을 효율적으로 처리하는 방법으로는 lazy propagation을 이용한 segment tree가 있다. 다만, 나도 이 개념을 아직 명확하게 이해하지 못한 상태이고, 단지 이럴 때 이 방법을 사용한다는 것만 알아놓은 상태이다.
따라서 이 개념에 대한 설명은 백준의 BOJ book 링크를 첨부한다. 코드도 보지 않고 짤 수 있는 수준이 아니라서 적당한 검색으로 느리게 갱신되는 세그먼트 트리 코드 함수들을 가져왔다.
3. 채점 결과
4. 회고
.
댓글남기기