백준 1663 XYZ 문자열 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/1663

1663번: XYZ 문자열

문제

"XYZ 문자열"이란 아래와 같은 문법에 의해 단계별로 만들어지는 일련의 문자열들을 뜻한다.

1. "XYZ 문자열"은 세 개의 문자 X, Y, Z로만 이루어진다.
2. 1단계 "XYZ 문자열"은 X로 시작한다.
3. 다음 단계의 "XYZ 문자열"은 바로 이전 단계의 "XYZ 문자열"에서 아래와 같은 규칙에 따라 변형되어 만들어진다.
   • X는 YZ로 변형된다.
   • Y는 Z로 변형된다.
   • Z는 X로 변형된다.

위와 같은 문법에 따라 1단계부터 몇 단계의 "XYZ 문자열"을 차례로 적어 보면 아래와 같다.

1. X
2. YZ
3. ZX
4. XYZ
5. YZZX
6. ZXXYZ

N단계의 "XYZ 문자열"과 관련해서, 아래의 문제 중 하나를 푸는 프로그램을 작성하시오.

1. N단계의 XYZ 문자열의 길이를 구한다.
2. N단계의 XYZ 문자열에서 k번째 문자가 무엇인지 구한다.
3. N단계의 XYZ 문자열에서 특정한 문자가 몇 번 나타나는지 구한다.

입력

첫째 줄에 문제 번호가 주어진다. 이는 1, 2, 3 중 하나이다. 이어서 둘째 줄에 자연수 N(1 ≤ N ≤ 100)이 주어진다. 문제 2인 경우는 셋째 줄에 자연수 k가, 문제 3인 경우는 셋째 줄에 X 또는 Y 또는 Z가 주어진다. k는 항상 N번째 문자열의 길이보다 작거나 같다.

출력

문제 1인 경우는 길이를 나타내는 정수를, 문제 2인 경우는 k번째 문자를, 문제 3인 경우는 특정한 문자가 나타난 횟수를 각각 첫째 줄에 출력하면 된다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제 풀이할 때마다 하는 소리다.

dp는 구현 자체는 어렵지 않은데, 그 점화식을 세우기, 점화식을 세우기 위한 규칙 찾기가 '다'이다.

하지만 그 '다'가 너무 어려운 dp이다.

dp는 dp문제인지 알아내는 것부터 문제!

 

문제의 조건 중 '2. N단계의 XYZ 문자열에서 k번째 문자가 무엇인지 구한다.'는 싸피 적성진단에 ct로도 나온 적이 있다고 한다.

 

본인은 처음에 '이거 되나?' 식으로 무지성 재귀를 돌렸다.

결과는 메모리 초과

뭐지 싶어서 알고리즘 분류를 보고 그제서야 DP문제라는 걸 알았다.

DP는 항상 이런식이야.. 

 

 

우선 주어진 N이 5라고 하면, 1, 2, 3, 4, 5 총 5단계로 문자열이 변형된다.

이 변형되는 단계들을 뎁스(depth)라고 하자.

뎁스1일 땐 X

뎁스2일 땐 YZ

뎁스3일 땐 ZX

뎁스4일 땐 XYZ

뎁스5일 땐 YZZX

뎁스6일 땐 ZXXYZ

뎁스7일 땐 XYZYZZX

뎁스8일 땐 YZZXZXXYZ

.

.

.

뎁스 100일 땐 ?

뎁스 50의 길이가 십몇 만 이었던 거 같고, 100일 땐 INT 범위를 초과하니 재귀를 이용해 문자열을 구한 풀이는 메모리 초과가 나올 수 밖에 없었다.

따라서 우리는 문자열을 직접 구할 순 없고, 기저 사례의 문자열을 가지고 규칙을 찾아 dp를 만들어나가야 한다.

 

별의별 규칙을 다 찾았는데 결국 쓸모 있는 규칙은 다음과 같다.

뎁스 1,2,3일 땐 문제에서 주어줬고,

뎁스4일 때는 X + YZ

뎁스5일 때는 YZ + ZX

뎁스6일 때는 ZX + XYZ

뎁스7일 때는 XYZ + YZZX

뎁스8일 때는 YZZX + ZXXYZ

규칙이 보이는가

뎁스 i의 문자열은 뎁스[i-3]+뎁스[i-2]과 같다!!!!

이제 문제는 다 풀었다. 구현만 하면 된다.

 

long long dp[i] = 뎁스가 i일 때 문자열의 길이

long long cnt[i][3] = 뎁스가 i일 때 X,Y,Z각각의 개수 (cnt라 이름을 지었지만 마찬가지로 dp이다)

위의 두 개 배열을 준비한 후,

기저 사례로 뎁스 1,2,3인 경우를 각각 넣어주자.

이후 뎁스가 4일 때부터 n까지 점화식

dp[i] = dp[i-3]+dp[i-2];

cnt[i][j] = cnt[i-3][j-3] + cnt[i-2][j-2];

로 dp,cnt를 채워준다.

이것만으로 문제 1인 경우(뎁스가 n일 때 문자열의 길이)와 문제 3인 경우(뎁스가 n일 때 특정한 문자의 개수)는 구할 수 있다.

문제 2의 경우(뎁스가 n일 때 a번 째 인덱스의 문자는?)는 이분 탐색으로 찾을 수 있다.

우리는 기저 사례를 통해 뎁스가 1,2,3일 때 문자열이 각각 X, YZ, ZX라는 걸 안다.

뎁스가 8이고 6번째 문자를 찾는다고 해 보자.

 

depth=8

findIdx =6

1234    56789

YZZX + ZXXYZ 

 

현재 6번째 문자는 depth를 depth-3 + depth-2로 나타냈을 때 depth-2에 포함되어 있다.

그러면 depth-3은 버리고 depth-2로 탐색 범위를 좁힐 수 있다.

 

depth=6

findIdx=2

12 345

ZX XYZ

현재 2번째 문자는 depth-3에 있으니 또 범위를 줄일 수 있다.

 

depth=3

findIdx=2

12

ZX

현재 depth<=3으로, 기저사례에 해당한다. 고로 기저 사례의 문자열은 미리 저장해둔 문자열로 바로 찾을 수 있다.

 

아마 이 문제가 골드1인 것은 DP문제라는 것과, 문제 2의 조건 때문일 것이다.

하지만 문제 1과 문제 3을 풀었다면 문제 2도 어렵지 않게 풀 수 있을 것이다!

코드

#include <iostream>
#include <string>

using namespace std;

//1<=n<=100
string base[4];
long long dp[101];
long long answer = 0;
long long cnt[101][3];


char solve(long long idx,int depth) {
	if (depth <= 3) {
		return base[depth][idx - 1];
	}

	if (dp[depth - 3] >= idx) {
		return solve(idx, depth - 3);
	}
	else {
		return solve(idx - dp[depth - 3], depth - 2);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t, n;


	cin >> t >> n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 2;
	base[1] = "X";
	base[2] = "YZ";
	base[3] = "ZX";
	cnt[1][0] = 1;
	cnt[2][1] = cnt[2][2] = 1;
	cnt[3][0] = cnt[3][2] = 1;
	for (int i = 4; i <= n; i++) {
		dp[i] = dp[i - 3] + dp[i - 2];
		for (int j = 0; j < 3; j++) {
			cnt[i][j] = cnt[i - 3][j]+cnt[i-2][j];
		}
	}
	
	if (t == 1) {
		cout << dp[n];
	}
	else if (t == 2) {
		long long k;
		cin >> k;
		//k번째 문자가 무엇인지
		cout << solve(k, n);
	}
	else {
		char ch;
		cin >> ch;
		cout << cnt[n][ch - 'X'];
	}

	return 0;
}