쌓고 쌓다

[백준] 사전 1256번 C++ 풀이 본문

알고리즘/백준

[백준] 사전 1256번 C++ 풀이

승민아 2022. 3. 8. 20:12

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

 

1256번: 사전

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되

www.acmicpc.net

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
long long dp[101][101];
int N, M, K;
string res = "";
long long Count(int a, int z)
{
	if (a == 0 || z == 0)
		return 1;
	if (dp[a][z] != 0)
		return dp[a][z];

	return dp[a][z] = min(Count(a - 1, z) + Count(a, z - 1),(long long)1000000001);
}

void solve(int a, int z, int k)
{
	if (a == 0)
	{
		for (int i = 0; i < z; i++)
			res +="z";
		return;
	}
	if (z == 0)
	{
		for (int i = 0; i < a; i++)
			res+="a";
		return;
	}

	long long check = Count(a - 1, z);
	if (k > check)
	{
		res+= "z";
		solve(a, z - 1, k - check);
	}
	else
	{
		res+="a";
		solve(a - 1, z, k);
	}
}
int main(void)
{
	cin >> N >> M >> K;
	solve(N, M, K);

	if (Count(N,M) < K)
		cout << "-1";
	else
		cout << res;
        
       //아래는 혼자 그냥 dp배열 확인을 위한 코드 
	/*cout << endl << endl;

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++)
			cout << dp[i][j] << " ";
		cout << endl;
	}*/
}

 

도통 이해가 안갔는데 아래 블로그가 큰 도움이 되었다..

아래 블로그의 설명을 참조하시길~

https://degurii.tistory.com/164

 

저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 외계인의 기타 연주 2841번 C++풀이  (0) 2022.03.23
[백준] 퇴사 2 15486번 C++ 풀이  (0) 2022.03.10
[백준] 행성 터널 2887번 C++ 풀이  (0) 2022.02.12
[백준] 미로만들기 2665번 C++ 풀이  (0) 2022.02.07
[백준] 숫자고르기 2668번 C++ 풀이  (0) 2022.02.01
'알고리즘/백준' Related Articles more
Comments