백준 2900 프로그램(파이썬)

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

2900번: 프로그램

풀이

문제를 푸는 로직은 단순하나 중복되는 곳을 찾아서 최적화하는게 문제 풀이의 핵심였다.

나는 중복되는 곳을 두군데를 찾아 최적화를 진행하였는데 하나는 "something"이라는 문제에서 제시해준 함수이고 나머지 하나는 구간 사이의 총합을 구하는 함수이다.

문제에서 원하는 답을 구하기 위해서는 X1, X2, X3, ... Xk의 간격을 지닌채 a배열의 원소에 +1씩 해야한다. 나는 이곳해서 동일한 간격 즉 x의 배열에서 동일한 값들을 가진 원소들의 수를 확인해서 중복을 없앴다. 이후 a배열의 원소에 +1씩하는 것이 아닌 +중복된 원소의 수 만큼 더해주었다. 그리하여 첫번째 중복을 제거 하였다.

두번째 중복은 구간내의 합을 구하는 함수이다. 나는 a배열에서 누적합을 인덱스 별로 미리 구해놓았다. 이후 L, R이 입력될 경우 값을 R인덱스의 누적합 - L인덱스의 누적합 으로 값을 구했다.