오늘의 문제 : 수열과 쿼리 13

https://www.acmicpc.net/problem/13925

난이도가 점점 막장이 되어가고 있는 것으로 유명한 수쿼 시리즈에 속해있는 문제이다.(요즘 나오는 수쿼들은 solved.ac 기준 난이도가 죄다 다이아2~루비 수준...) 하지만 이 문제처럼 숫자가 10대인 문제들은 아직 난이도가 막장이 되기 전의 문제들이 많다. 물론 나는 그것도 거의 못 풀지만...ㅠ 

그 중에 수열과 쿼리 13은 세그먼트 트리 레이지 프로퍼게이션을 이용하는 문제다. 내가 고급 알고리즘 중에서는 그나마 제일 좋아하는 게 레이지 프로퍼게이션이다. 컨벡스 헐, KMP 이딴것보다는 훨씬 낫다.

레이지 프로퍼게이션을 이용하는 것만 알면 일단 반은 푼 거였다. 그리고 나머지 반은 오늘 아침 학교에 가서 골똘히 생각해보았다.

일단 구해야 하는 쿼리가 합이므로 덧셈 세그를 짜야할 것이다. 그리고 덧셈 레이지와 곱셈 레이지를 따로 만들어줘야 할 것이다. 문제는 3번 쿼리인데, 오랜 생각 끝에 결국 답을 찾을 수 있었다. 먼저 0을 곱하고 v만큼 더하면 모든 수가 v가 된다는 것이었다. 어찌 보면 아주 간단한 아이디어인데 그걸 생각하기가 참 힘들었다.

하교 후에 바로 코딩을 시작했다. 이미 로직은 머릿속으로 다 짜놔서 코딩은 일사천리였다. 실수 몇 개가 발목을 잡기는 했지만 결국 AC를 받을 수 있었다.

풀이는 이렇다.

곱레이지와 합레이지를 따로 만든다. 그 레이지가 의미하는 바는 지금 이 배열의 값에 곱레이지만큼을 곱한 다음 합레이지만큼을 더할 것이라는 의미다. 그러므로 일단 곱레이지와 합레이지의 디폴트 값은 각각 1과 0이 되어야 할 것이다. 그리고 쿼리가 들어올 때마다 적당히 레이지를 만들어주면 된다. 그건 쉽다. 핵심은 프로퍼게이션이다. propagate할 때는 절대 합레이지도 곱레이지로 곱해주는 걸 잊어서는 안 된다. 간단히 수식으로 보면 ax+b에 c를 곱하고 d를 더하면 acx+bc+d가 되는 것으로 바로 알 수 있다. 합레이지를 의미하는 b에도 c가 곱해진 걸 알 수 있다. 곱레이지는 0이 아닌 1로 초기화한다는 걸 신경쓰면서 코딩을 완료해주면 된다.

 

코드링크 : http://boj.kr/390d475553bc4e79af12d76e19a7993b

공유 소스 보기