[백준 2900번] 파이썬 - 프로그램

백준 2900 - 프로그램

시간 제한 2초, 메모리 제한 256MB

# 조건

• 창영이가 에러를 찾기 위해서 디버깅을 하고 있다.
• 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다.

void something(int jump) {
    int i = 0;
    while (i < N) {
        a[i] = a[i] + 1;
        i = i + jump;
    }
}

• 창영이는 함수를 K번 호출하려고 한다.
• 각각 호출할 때, 인자로 넘기는 jump의 값은 X1, X2, X3, ... Xk 순서이다.
• 이렇게 호출한 뒤에는 배열의 값이 정상적으로 들어갔는지를 확인하려고 한다.
• 확인은 총 Q번 하고, 매번 확인을 할 때마다 L과 R(L ≤ R)을 정한뒤, 그 구간의 배열의 합을 구한다.
  • 즉, a[L] + a[L+1] + ... + a[R]을 구한다.
• 함수를 호출할 때 필요한 X의 값과 창영이가 확인한 횟수 Q가 주어졌을 때, 확인한 결과(배열의 합)을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 배열의 크기 N과 함수의 호출 횟수 K가 주어진다. (1 ≤ N, K ≤ 10^6)
• 둘째 줄에 함수를 호출할 때 사용하는 인자의 값 X1, X2..., Xk가 공백으로 구분되어 주어진다. (1 ≤ Xi < N)
• 셋째 줄에는 확인하는 횟수 Q가 주어진다. (1 ≤ Q ≤ 10^6)
• 넷째 줄부터 Q개 줄에는 각 확인에 사용하는 L과 R이 주어진다. (0 ≤ L ≤ R < N)

출력

• 출력은 총 Q줄이다.
• 창영이가 확인하는데 사용한 L과 R이 주어졌을 때, a[L] + a[L+1] + a[L+2] ... + a[R]을 출력한다.

# 접근 방법

• 우선 주어지는 something 함수를 풀이할 언어에 맞게 변경하여 정의해준다.
• 구간의 합을 확인하는 문제이므로 누적합을 이용해준다.
• something함수를 K번 호출한다면 100만번까지 가능하므로, Counter 함수를 이용해준다.
  • 주어진 jump의 숫자들이 몇 번씩 등장하는지 Counter를 이용하여 딕셔너리로 구해준다.
  • Counter를 순회하며 jump의 값과 등장 횟수를 something 함수로 넘겨준다.
  • 따라서, something 함수에서 +1이 + 등장 횟수로 변경된다.
• 이후, 완성된 arr의 누적합을 구한 뒤 주어지는 구간의 합을 출력하면 된다.
  • 주어지는 구간이 처음이 주어질 수 있으므로 prefix의 제일 뒤에 0을 붙여준다.
    • 즉, 시작과 끝까지의 구간을 구하라한다면 prefix[end] - prefix[-1]을 수행해주면 제일 뒤가 0이므로
    • 처음과 끝의 구간 합을 구해줄 수 있다.

import sys  
input = sys.stdin.readline  
from collections import Counter  

def main():  
    def something(j, v):  
        i = 0  
        while i < N:  
            arr[i] += v  
            i += j  
    N, K = map(int, input().split())  
    arr = [0] * N  
    jump = list(map(int, input().split()))  
    cnt = Counter(jump)  

    for k in cnt:  
        something(k, cnt[k])  
    prefix = [0] * (N+1)  
    prefix[0] = arr[0]  
    for i in range(1, N):  
        prefix[i] = prefix[i-1] + arr[i]  
    for _ in range(int(input())):  
        a, b = map(int, input().split())  
        print(prefix[b] - prefix[a-1])  

if __name__ == '__main__':  
    main()