[백준 2042번] 구간 합 구하기

난이도: 골드 I

문제 링크: https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

백준 2042번 문제 구간 합 구하기

이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다.

기본적인 설명은 여기를 참고해 주세요.

 

세그먼트 트리의 기본적인 문제입니다.

한 가지 유의할 점이 있다면, 값을 수정할 때입니다.

b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다.

따라서 차이값 difference  =  c - arr[b]가 되며, 차이값을 구할 때 arr을 참조하므로, arr[b]의 값 역시 수정하는 작업이 필요합니다.

이 외에는 세그먼트 트리 설명글과 거의 같으니 생략하겠습니다.

 

보통 이 문제는 채점 중 5% 지점에서 틀렸습니다 판정이 많이 나오는데,

앞서 말한 arr[b] 값 수정이 주된 원인이고, 또 하나는 tree의 크기를 너무 작게 잡으면 오답처리가 됩니다.

채점 결과

저도 위에서 언급한 두 부분에서 문제가 되어서 오답 판정을 여러 번 받았습니다 ㅠㅠ

세그먼트 트리의 가장 기초적인 문제라고 할 수 있는데 난이도가 골드 1이나 된다니... 실수할 여지가 많긴 하네요.