백준 26156: 나락도 락이다 아이디어 & 코드

아이디어

뒤에서부터 보면서 'K', 'C', 'O'를 찾으면서

각 인덱스에서 "OCK"를 만들 수 있는 경우의 수를 구한다

 

그리고 값이 'R'인 모든 인덱스에서,

그 인덱스에서

1.  "OCK"를 만들 수 있는 경우의 수와

그 인덱스의

2. 앞에 있는 문자의 개수만큼 2의 거듭제곱을 한 값을 구한다.

그리고 1과 2를 곱해 나온 값을 모두 더하면 답이 나온다

 

쉽게 이해하려면 R인 인덱스 기준으로 보면 된다

1. R인 인덱스 뒤에서 "OCK"를 만들 수 있는 경우의 수 -> 그 R을 가지고 ROCK을 만들 수 있는 경우의 수

2. 앞에 있는 문자의 개수만큼 2의 거듭제곱을 한 값 -> R 앞에 있는 문자 모두를 넣거나 넣지 않거나 하는 경우의 수

1과 2를 곱하면 그 R을 기준으로 가능한 ROCK으로 끝나는 문자열의 경우의 수가 나오는 것이다

 

 

 

위의 아이디어를 구현하기 위해서 DP를 이용한다

채워나갈 배열은 다음과 같이 설정했다

 

DP[0][idx] -> 전체 문자열 S의 부분 문자열 S[idx~N)에 있는 "K"의 경우의 수

DP[1][idx] -> 전체 문자열 S의 부분 문자열 S[idx~N)에 있는 "CK"의 경우의 수

DP[2][idx] -> 전체 문자열 S의 부분 문자열 S[idx~N)에 있는 "OCK"의 경우의 수

 

우리가 관심있는 배열은 DP[2][idx]이다. DP[0][idx], DP[1][idx]는 얘를 만들기 위한 배열임.

DP[2][idx]를 완성한 뒤

S[idx] == 'R'인 모든 idx에 대하여 (2의 idx제곱) * (DP[2][idx])를 구해 모두 합하면 답이 된다.

 

물론 경우의 수가 아주 많기 때문에 모듈러 연산에 신경써주어야 한다.

 

코드

#include <iostream>
#define ll long long
#define MOD 1'000'000'007
using namespace std;

int N;
string S;
ll DP[3][1'000'000] = { 0, }; //DP[k][idx] -> S[idx..N) 중에서 KCOR와 k개 일치하는 부분열의 개수 

ll squareTwo(int n) {
	ll total = 1;
	if (n < 30)
		return (total << n);

	if (n % 2)
		return ((squareTwo(n / 2) * squareTwo(n / 2) * 2) % MOD);
	else
		return ((squareTwo(n / 2) * squareTwo(n / 2)) % MOD);
}

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

	cin >> N;
	cin >> S;

	DP[2][N - 1] = 0;
	DP[1][N - 1] = 0;
	if (S[N - 1] == 'K')
		DP[0][N - 1] = 1;
	else
		DP[0][N - 1] = 0;

	for (int i = N - 2; i >= 0; i--) {
		if (S[i] == 'K')
			DP[0][i] = ((DP[0][i + 1] + 1) % MOD);
		else 
			DP[0][i] = DP[0][i + 1];

		if (S[i] == 'C')
			DP[1][i] = ((DP[1][i + 1] + DP[0][i + 1]) % MOD);
		else
			DP[1][i] = DP[1][i + 1];

		if (S[i] == 'O')
			DP[2][i] = ((DP[2][i + 1] + DP[1][i + 1]) % MOD);
		else
			DP[2][i] = DP[2][i + 1];
	}

	
	ll total = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (S[i] == 'R') {
			total += ((squareTwo(i) * DP[2][i]) % MOD);
			total %= MOD;
		}
	}

	cout << total << '\n';

	return 0;
}

DP[0]의 경우 그냥 K가 보일 때마다 1씩 더해주면 되고

DP[1]의 경우 C가 보일 때마다 그 이전 인덱스의 DP[0]의 값을 더해주면 되고

DP[2]도 C와 같이 O가 보일 때마다 그 이전 인덱스의 DP[1]의 값을 더해주면 된다

DP 배열의 모든 값을 구할 때 모듈러 연산을 미리미리 해줘야 한다.

 

R이 나올 때마다 2의 거듭제곱과 DP 배열의 값을 더해주는 부분에서는

2의 거듭제곱이 나오는 부분을 신경써줘야 한다

최대 2의 1,000,000 거듭제곱을 구해줘야 하는데, 당연히 이 값을 구하는 건 말이 안되고

모듈러의 성질을 이용한 분할정복 코드를 작성해줬다

 

좀 더 발전된 아이디어

앞서 이용했던 아이디어의 DP 배열을 확인해보면

원하는 문자가 나오지 않았을 때 그 이전 인덱스의 배열 값을 그대로 옮기는 비효율적인 부분을 확인할 수 있다

 

앞의 아이디어는 각 인덱스에 대해서 OCK의 개수에 2의 거듭제곱을 구하지만

이 아이디어는 OCK를 계속 합하면서 2를 제곱한다

 

배열 DP[4]가 있다

뒤에서부터 S를 확인하면서

1. DP[3] *= 2

2. 현재 S[i]가 K이면 DP[0]++

3. 현재 S[i]가 C이면 DP[1] += DP[0]

4. 현재 S[i]가 O이면 DP[2] += DP[1]

5. 현재 S[i]가 R이면 DP[3] += DP[2]

를 해주면

DP[3]이 답이된다

 

어떤 문자가 나오던 이전의 총합인 DP[3]에 2를 곱해주는 것에 주목하자

처음 DP[3]에 포함된 OCK의 경우의 수는 계속 2가 곱해질 것이고

나중에 들어간 OCK의 경우의 수는 몇 번 안 곱해진다

 

또한 DP 값을 업데이트 할 때마다 모듈러 연산 해주는 것을 잊지 말자

처음에 풀었던 방법은 DP 자체는 O(logN)이지만

2의 거듭제곱을 분할정복기법으로 구하기 때문에 O(NlogN)이다

이 방법은 2의 거듭제곱을 한 번에 구할 필요가 없이 한번에 2씩 곱하기만 하면 되기 때문에

DP만 보기 때문에 O(logN)이다.