백준 22957 짝수싫어수

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

22957번: 짝수싫어수

 

풀이 

1. DP정의

DP를 다음과 같이 정의하겠습니다.

DP[i][j] : DP[길이가 i인 상황][숫자의 상태가 j]인 상태의 경우의 수

 

위에서 숫자의 상태가 j라는 것은 3, 5, 7의 개수가 짝수인지 아닌지를 의미합니다.

ex)  100₂ : 7의 갯수가 짝수, 5의 개수가 짝수, 3의 개수가 홀수인 상태

.     101₂ : 7의 갯수가 홀수, 5의 개수가 짝수, 3의 개수가 홀수인 상태

 

 

i는 N이 30까지 나오기때문에 30까지 나올 것이고

j는 경우의 수가 0~7까지 이므로 8까지 나올 것입니다.

DP[30][8] 크기의 상태 DP를 만들 수 있습니다.

 

 

DP[i][j]의 다음 상태는 DP[i - 1][j^1], DP[i - 1][j^2], DP[i - 1][j^4]로 정의할 수 있고

(3,5,7의 개수가 변하는 것을 고려한 것입니다.)

 

 

점화식을 다음과 같이 정의할 수 있습니다.

DP[i][j] = DP[i-1][j^1] + DP[i-1][j^2] + DP[i-1][j^4];

 

점화식을 이용해서 DP 테이블을 채우면 됩니다.

 

 

---

2. DP를 사용하는 방법

DP를 구했지만 DP를 이용해서 답을 구하는 방법을 생각해봐야 합니다.

 

예시를 통해서 방법을 설명하겠습니다.

N = 6, K = 400인 상태에서 정답을 구하는 방법입니다.

정답으로 나올 수 있는수는  10^6이하인 수입니다. 최대 6자리까지 나올 수 있기 때문에 다음과 같이 표현하겠습니다.

 

정답을 구하기 위해서 해당 빈칸에 숫자를 넣을 수 있는지 확인해야 합니다.

그러기 위해서는 맨 앞자리가 특정 숫자일 경우 나올 수 있는 경우의 수를 알아야 되고 

구하는 방법은 다음과 같습니다.

int cnt[3] = { 0, };
for (int k = 0; k < 3; k++)
	for (int j = 0; j < 8; j++)
		if (fn != j)
		    cnt[k] += Dp(i - 1, j ^ (1 << k));

cnt[k] : 맨앞자리가 k번째 숫자인 상태의 경우의 수
fn : 현재 상태에서 도달하면 안되는 상태

 

처음은 아무 숫자도 배치하지 않았기 때문에 fn = 000₂인 경우는 제외해야 합니다.

fn = 000₂인 상태로 cnt를 갱신해주고 아래의 순서대로 배치를 할 수 있는지 검사합니다.

 

먼저 맨앞자리에 7이 올 수 있는지 부터 판단하겠습니다. cnt[0]은 현재 맨앞자리가 7인 경우의 수를 의미합니다. 여기선 cnt[0] = 182이므로 K보다 작습니다. (cnt[0] < K) (K = 400) 7은 맨 앞에 둘수 없습니다. K -= cnt[0]를 해줍니다. (k = 218) 맨앞에 5가 올 수 있는지 검사합니다. cnt[1]은 현재 맨앞자리가 5인 경우의 수를 의미합니다. cnt[1] = 182이므로 K보다 작습니다. (cnt[1] < K) (K = 218) 5은 맨 앞에 둘 수 없습니다. K -= cnt[1]를 해줍니다. (k = 36) 마찬가지로 3이 맨 앞에 올 수 있는지 검사합니다. cnt[2]도 현재 맨앞자리가 3인 경우의 수를 의미합니다. cnt[2] = 182입니다. K보다 큽니다. (cnt[1] > K) (K = 36) 3은 맨앞에 둘 수 있습니다. (만약 어떠한 숫자도 배치할 수 없으면 배치하지않고 넘어갑니다.)

 

 

3을 배치했으니 fn을 갱신해야 됩니다.

3이 홀수 5가 짝수 7이 짝수인 경우인 경우를 제외해야 합니다.

fn을 100₂로 갱신해줍니다 모든 자릿수마다 해당 방법으로 어떤 숫자가 와야 되는지 구해준다면

정답을 구할 수 있습니다.

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

using namespace std;

int DP[32][10];
int Dp(int n, int bit)
{
	if (n == 0)
	{
		if (bit == 0)
			return 1;
		else
			return 0;
	}

	if (DP[n][bit] != -1)
		return DP[n][bit];
	DP[n][bit] = 0;
	DP[n][bit] += Dp(n - 1, bit ^ 1) + Dp(n - 1, bit ^ 2) + Dp(n - 1, bit ^ 4);
	return DP[n][bit];
}

int N, K;
string Num[3] = { "7","5","3" };
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);

	memset(DP, -1, sizeof(DP));

	cin >> N >> K;

	int b = 0;

	int fn = 0;
	for (int i = N; i >= 1; i--)
	{
		int cnt[3] = { 0, };
		for (int k = 0; k < 3; k++)
			for (int j = 0; j < 8; j++)
				if (fn != j)
					cnt[k] += Dp(i - 1, j ^ (1 << k));

		for (int j = 0; j < 3; j++)
		{
			if (K > cnt[j])
				K -= cnt[j];
			else
			{
				cout << Num[j];
				fn ^= (1 << j);
				break;
			}
		}
	}

	cout << endl;
}