[C/C++] 백준 16139번 - 인간-컴퓨터 상호작용

✏️ 문제 링크

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

16139번: 인간-컴퓨터 상호작용

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

누적 합과 dp를 섞어서 푸는 문제입니다. 처음에는 그냥 브루투포스처럼 노가다로 돌리려고 했는데 연산 횟수가 4억번이라서 시간초과가 발생할 것 같아서 dp를 이용하기로 했습니다. 먼저 dp[200001][26]배열을 만듭니다. 이 dp 배열의 의미는

d[i][j]라고 했을 때, i번째 문자열까지 j알파벳이 나온 횟수를 의미합니다. 그리고 이 dp를 구성하기 위해서 ac배열과 cnt2배열을 만들어서 문자열에서 나오는 알파벳의 개수를 카운팅해주었습니다. dp테이블을 구성하는 방법입니다.

 

이중 반복문을 돌려주고 문자열의 길이를 돌려주고 그 안에서 알파벳의 개수(26개)만큼 돌려줍니다.

일치하는 알파벳이 있다면 d[i][j] =cnt2[a], cnt2[a]++을 해주고 일치하지 않는다면 dp[i][j] = dp[i-1][j]로 업데이트해줍니다.

구성을 다하고 l과 r을 입력받아서 답을 출력해줍니다. 문제에서는 문자열을 0번부터 시작한다고 했지만 저는 1번부터 시작하도록 하였으므로 정답을 dp[r+1][a] - dp[l][a]로 출력하였습니다.

 

✏️ 문제 코드

#include<iostream>
#include<string>
using namespace std;

int ac[26];
int cnt2[26];
int dp[200001][26];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string str;
	cin >> str;

	int len = str.length();
	for (int i = 0; i < len; i++) {
		char a = str[i];
		a -= 'a';
		ac[a]++;
	}
	fill(cnt2, cnt2 + 26, 1);

	int q;
	cin >> q;

	for (int i = 1; i <= len; i++) {
		char a = str[i - 1];
		a -= 'a';
		for (int j = 0; j < 26; j++) {
			if (a == j) {
				if (ac[a] >= cnt2[a]) {
					dp[i][a] = cnt2[a];
					cnt2[a]++;
				}			
			}
			else
				dp[i][j] = dp[i - 1][j];
		}
	}

	while (q--) {
		char a;
		cin >> a;
		a -= 'a';
		int l, r;
		cin >> l >> r;
		if (l == 0)
			cout << dp[r + 1][a] << '\n';
		else
			cout << dp[r + 1][a] - dp[l][a] << '\n';
	}
}