https://www.acmicpc.net/problem/11505
11505번: 구간 곱 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
세그먼트 트리 문제다.
풀이
구간 합 구하기 문제와 다른 점은 세그먼트 트리의 갱신 부분에 주의할 부분이 있다는 점이다. 처음에는 단순히 기존값으로 나누고, 새로운 값으로 다시 곱해주면서 리프노드까지 도달하는 방법으로 접근했지만, 예제에서 알 수 있듯이 트리의 값이 0으로 바뀌게 되면 다음 갱신에 문제가 발생한다. 따라서 리프노드부터 먼저 갱신이 이루어지고, 루트노드까지 새로운 값으로 계산을 해주어야 한다.
정답 코드
재귀호출 시에 범위를 반대로 적어 "틀렸습니다"를 연발했다.. 아는 유형의 문제라 방심했던 탓이다. 항상 집중해서 문제를 풀 것.
'Problem Solving > BOJ' 카테고리의 다른 글
| [1306] 달려라 홍준 (0) | 2023.02.18 |
|---|---|
| [14428] 수열과 쿼리 16 (0) | 2023.02.17 |
| [2357] 최솟값과 최댓값 (0) | 2023.02.15 |
| [2042] 구간 합 구하기 (0) | 2023.02.15 |
| [2533] 사회망 서비스(SNS) (0) | 2023.02.13 |