[BOJ 2900] 프로그램 C++

 

2900번: 프로그램

 

 

문제풀이

 

이 문제는 something이라는 함수를 k번 호출하고 구간 합을 구하는 문제다.

 

something 함수를 잘 보면 jump로 나누어 떨어지는 인덱스마다 1을 증가시키는 함수라는 것을 알 수 있다.

 

jump 인자를 하나씩 입력받으면서 해당 값이 몇 번 나왔는지 카운트한다.

인자가 0부터 시작해서 jump만큼 더해가기 때문에 a[0]은 무조건 k이다.

0을 제외한 jump로 나누어떨어지는 인덱스마다 그 값이 나온 횟수만큼 더해주면 something 함수를 k번 호출한 결과와 같다.

 

이후에 누적 합을 저장하는데 N과 K가 최대 1,000,000이기 때문에 배열 a를 long long으로 선언해주었다.

L이 0일 때는 a[right], 그 외의 경우에는 a[right] - a[left - 1]이 그 구간의 배열의 합이 된다.

 

 

C++ 코드