인간-컴퓨터 상호작용 (feat. 백준, 16139번)

인간-컴퓨터 상호작용
https://www.acmicpc.net/problem/16139

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

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cstring>
#include <string.h>
using namespace std;
int dp[26][200002];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	memset(dp, 0, sizeof(dp));
	string str;
	cin >> str;
	for (register int i = str.size() - 1; i >= 0; --i)
		for (register int c = 0; c < 26; ++c) {
			dp[c][i] = dp[c][i + 1];
			if (c == (str.at(i) - 'a'))
				++dp[c][i];
		}
	register int N, l, r;
	char tmp;
	cin >> N;
	for (register int n = 0; n < N; ++n) {
		cin >> tmp >> l >> r;
		cout << dp[tmp - 'a'][l] - dp[tmp - 'a'][r + 1] << "\n";
	}
	return 0;
}
// *&)*@*

1. 문자와 l, r을 받을때마다 dp를 구하는 형태는 50점의 결과를 얻습니다.
2. 따라서 모든 문자 (a부터 z까지 26개의 문자) 에 대한 dp를 문자열에 대해서 미리 만들고, 입력받은 l,r 에 대해서 구해주면 됩니다.
3. 해당 문제는 아래 문제에서 단순히 문자열 26개로 확장 (1차원 배열에서 2차원 배열로) 된 개념이므로 미리 풀어보시길 권장합니다.

수열 (feat. 백준, 2559번)