[BOJ 27914 // C++] 인터뷰

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27914번 문제인 인터뷰이다.
문제는 아래 링크를 확인하자.

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

27914번: 인터뷰

\(a_n\)을 앞 \(n\)명에 대해 가능한 인터뷰의 경우의 수라 정의하자. 이 때, 앞 \(n\)명에 대해 가능한 인터뷰는 (i) 앞 \(n-1\)명에 대해서 가능한 인터뷰에 포함되거나 (ii) \(n\)번째 학생을 포함하는 두 경우로 나누어 생각할 수 있다.

 

(i)의 경우 그 값은 \(a_{n-1}\)과 같고, (ii)의 경우 그 값은 \(n\)번째 학생부터 시작해 왼쪽으로 존재하는 연속한 "K학년이 아닌 학생"의 수로 구할 수 있다. 이를 이용해 점화식을 세워 문제를 해결하자. 아래 구현의 combo와 같은 변수를 이용하면 그 구현을 용이하게 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, K, Q;
ll ans[100001], combo;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K >> Q;
	
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (K == x) combo = 0;
		else combo++;
		ans[i] = ans[i - 1] + combo;
	}

	while (Q--) {
		int q; cin >> q;
		cout << ans[q] << '\n';
	}
}