[백준 2900번] 프로그램

난이도: 골드 II

문제 링크: https://www.acmicpc.net/problem/2900

2900번: 프로그램

백준 2900번 문제 프로그램

 

위 문제를 접하고 정말 단순하게 구현하면, 구현은 됩니다.

something 함수를 K번만큼 호출하고, 부분합을 구하기 위해 Q번만큼 합을 구합니다.

something 함수를 보시면 loop를 N번 반복하게 되어 있고, 부분합을 구할 때 L = 0, R = N이라면 배열에 N번 접근하게 됩니다.

K, N, Q는 10^6 이하입니다.

따라서 두 경우 모두 별도의 방법을 생각하지 않으면 시간 초과가 나게 됩니다.

 

맨 첫 번째, something 함수를 K번만큼 호출하는 부분을 보면, 원소가 중복되는 경우를 생각해 볼 수 있습니다.

원소가 총 10^6개 있고, 모두 값이 3이라고 합시다.

기존의 방법대로 수행한다면 함수를 10^6번 실행하여, a[i] = a[i] + 1을 매번 수행하게 됩니다.

하지만 모든 원소의 값이 같으므로, 이를 따로 센 후에 함수를 한 번만 실행해도 같은 값을 얻을 수 있습니다.

cnt = 값이 3인 원소의 개수라고 하면, a[i] = a[i] + cnt를 하면 됩니다.

이렇게 하면 최선의 경우 O(N), 최악의 경우 여전히 O(KN)이지만, 많은 경우 시간복잡도를 줄일 수 있습니다.

위의 아이디어를 구현하기 위해서는 각 원소값의 등장횟수를 세어야 합니다. 이를 위하여 map 자료구조를 이용합니다.

 

두 번째, 부분합을 구하는 부분은, 부분합 배열을 별도로 미리 만들어 두는 방법이 있습니다.

부분합을 만들 때는 O(N)의 시간복잡도를 가지지만, 만들어 둔 배열에 접근하여 원하는 구간의 부분합을 구할 때는 O(1)의 시간복잡도를 가지게 됩니다.

예를 들어 배열의 총 길이가 5이며, 구간합 3~4를 원한다면, 다음과 같이 접근합니다.

• 배열의 인덱스 1에는 원소 1의 값, 인덱스  2에는 원소 1~2의 합, 인덱스 3에는 원소 1~3의 값... 이 기록됩니다.
• 이렇게 인덱스 5에는 원소 1~5의 합이 들어 있습니다.
• 구간합 3~4를 원한다면, 배열의 인덱스 4의 값에서 배열의 인덱스 (3-1)의 값을 빼면 됩니다. 즉 1,2,3,4의 합이 담긴 값에서 1,2의 합이 담긴 값을 빼므로 3,4의 합만 남는 것입니다.

 

코드로 구현하면 아래와 같습니다.

 

시간복잡도의 문제가 되는 두 부분을 짚어서 해결하는 것이 본 문제의 핵심이라고 생각합니다.

 

위의 기법을 적용해도 여전히 시간이 오래 걸리는 것을 확인할 수 있습니다.

물론 저보다 더 빨리 해결하신 분들도 많이 계십니다 ㅎㅎ.