[BOJ] 백준 1275번 : 커피숍2 (JAVA)

문제

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

 

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

 

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

 

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

 

 

입력

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

 

입력되는 모든 수는 32비트 부호있는 정수이다.

 

 

출력

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

 

노트

x~y는 당연히 x번째 부터 y번째가 맞다. 하지만, 이 문제에서는 x > y인 경우 y번째 부터 x번째이다.

 

 

풀이

세그먼트 트리를 이용한 문제였습니다.

 

사실, 문제의 맨 밑에 "노트" 라고 적혀있는 부분만 잘 읽었으면 세그먼트 트리의 입문할 때 배웠던 "2042번 구간 합 구하기" 문제와 거의 일치합니다.

 

"노트"에서는 x ~ y 가 주어질 때, 항상 x < y가 아니라, x > y 인 입력값도 들어옴을 암시하였습니다. 따라서, 이 부분만 주의하여 x > y 인 경우 x와 y의 값을 서로 뒤바꾸는 형식으로 코드를 짜시면 됩니다.

 

나머지는 흔히 사용하던 init, sum, update 메소드를 그대로 사용하셔도 문제를 풀 수 있습니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.