[2021 acm-icpc] 5/15 연습 문제

 

1. 백준 1086 박성원 (Platinum V - bitmask dp 문제)

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

1086번: 박성원

문제

 

N개의 수로 이루어진 집합이 주어진다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있는데,

합친 수가 정수 K로 나누어 떨어지는 순열의 개수를 구하는 문제이다.

 

* 테스트 케이스 설명

집합 {3, 2, 1} 이 주어졌는데, 이 집합으로 만들 수 있는 순열은 다음과 같이 6가지 되시겠다.

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}

예제에서 K=2 이므로 끝에 2가 들어가 있는 {1,3,2}, {3,1,2} 두 가지만 가능하겠다.

 

풀이

 

이 문제는 3가지 부분 문제가 포함되어 있다고 볼 수 있다.

 

• 무려 길이가 최대 50인 자연수에 K로 나눈 나머지를 어떻게 구할 것인가
• 기약 분수 형태 출력은 어떻게 하는 게 빠를까?
• 위에 두 개 알았는데.. 그래서 어떻게 푸는데..?

 

우선 하나씩 해결해보자.

 

1. 큰 수(BigInteger) 나누기

 

우린 초등학교 3학년 때 구구단을 외우고, 4학년 때 나누는 방법을 배운다.

초4 수환이 큰 수 111111을 3으로 나누면 이런 방식으로 나눌 것이다.

이 과정을 살짝 프로그래밍적으로 분석하면 과정은 이러하다.

 

1. 가장 앞자리 (자릿수가 가장 큰)부터 시작한다.
2. 갖고 있는 수에 10을 곱한 후, 현재 자리에 있는 수를 더한다.
3. 만약 현재 제수(divisor) 보다 갖고 있는 수가 크다면, 갖고 있는 수를 제수로 나눈 몫이 위로 올라가고, 나머지는 갖고 있는 수가 된다.
4. 3번을 거쳤거나, 작다면 다시 2번으로 되돌아간다.
5. 이 과정을 가장 마지막 자릿수까지 반복한다. 

 

일반적으로 우리가 "/" 기호를 사용하면 이 과정이 자동으로 O(1) 시간에 해결되지만, 만약 수가 10^50이라면 우리는 이 수를 문자열로 받고, 위 과정을 수작업으로 해줘야 한다.
그렇지만 생각보다 어렵지 않고 시간 복잡도는 O(|S|) (|S| : 문자열 길이)가 된다.

 

예시 코드

//x를 k로 나눈 나머지 반환
int rem(string x) {
	int tmp = 0;
	for (int i = 0; i < x.size(); i++) {
		tmp *= 10;
		tmp += x[i] - '0';
		tmp %= k;
	}
	return tmp;
}

 

 

2. 기약 분수 출력

 

나름 웰노운하지만, 이 글을 보시는 분들은 아주 다양하니 스킵하지 않고 설명을 적도록 하겠다.

만약 기약 분수가 아닌 분수 P/Q 가 있을 때, 기약 분수로 만드는 방법은 간단하다.

P, Q의 최대 공약수를 구한 후, P, Q 각각을 최대 공약수로 나누어주면 된다.

 

최대 공약수는 유클리드 호제법에 의해서 log(P + Q) 이므로 이 부분은 어떤 수가 나와도 대부분 가능하다.

 

* 참고) 유클리드 호제법 최대 공약수 구하는 코드

 

소스 코드(.cpp)

int gcd(int a, int b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

 

 

3. 이제 어떡하지..

 

문제에서 주어지는 집합의 수의 개수 N은 최대 15라서 모든 순열을 구하면 15! 가짓수가 된다.

참고로 보통 우리가 팩토리얼 시간 복잡도를 계산할 때 12! 부터는 1억이 가볍게 넘어가므로 안된다고 생각하는 게 좋다.

 

그럼 모든 가짓수를 일일이 계산하지 않고도 구할 수 있는 방법을 생각해봐야 한다.

 

내가 생각하던 중 떠오른 아이디어는 이렇다.

 

• (k로 나누어 떨어지는 수)를 여러 개 막 붙여도 k로 나누어 떨어지는구나!
• k가 3이고, 어떤 수 A라 할 때 3으로 나눈 나머지가 1인 수 (1, 4, 7, 10,...)를 A 뒤에 붙여도 k로 나눈 나머지는 똑같구나!

 

나는 첫 번째 아이디어에서 시작해 두 번째 아이디어로 왔었다.

그렇다면 이 아이디어에서 우리는 시간을 줄일 수 있는 방법을 생각해볼 수 있는데
방법은 이렇다.

굳이 모든 순열을 구해줄 필요 없이, 순서를 기록할 필요 없이 현재까지 어떤 수들을 골라 붙여놨고, 그 수들의 조합이 형성한 나머지의 개수를 알면 다음 수를 붙일 때 (나머지 + 다음수) 끼리 붙으니 나머지들을 고려해서 바로바로 구해줄 수 있다는 것이다.

 

말이 어려울 수 있는데.. dp table을 만들어보면 이런 식이다.

 

• dp[i][j] : 현재 상태(i)에서 k로 나눈 나머지가 j인 순열의 가짓수

 

이때, 현재 상태 i는 N이 최대 15이므로 비트로 표현할 수 있는데

만약 N이 3이고 첫 번째 수만 골랐다면 100

모든 수를 골랐다면 111

두 번째 수만 골랐다면 010

... 이런 식으로 표현하는 방법이다. 총 2^15(약 3만) 가지로, 생각보다 큰 수는 아니다.

   

그렇다면 문제에서 예제 케이스 집합 {3, 2, 1} 이 주어졌을 때 모든 수를 고른 dp table의 상태는 이렇다.

dp[7][0] = 2 ({1,3,2}, {3,1,2}) (비트 "111" = 7)

dp[7][1] = 4 (이외 나머지)

 

만약 이 상태에서 집합의 맨 앞에 "4"라는 수가 추가될 때 ({4, 3, 2, 1}) dp table의 변화는 이렇다.

dp[7][0] -> 0에 4를 추가하면 나누어 떨어짐, dp[5 + (1<<4)][0] += dp[5][0]

dp[7][1] -> 1에 4를 붙여도 여전히 나머지 1, dp[5 + (1<<4)][1] += dp[5][1]

 

만약 "3"이라는 수를 추가하면 반대로 dp[i+1][0] 에 dp[i][1] 이 추가될 것이다.

 

이런 식으로 그 전 상태의 나머지와 현재의 수를 붙여서 현재 상태 dp table을 완성시켜주면 된다.

 

시간 복잡도는 우선 dp table 만큼 O(2^N x K)에 각 상태마다 다음 상태를 선정 (다음 수를 고르기) 하는 데 N번 반복되므로 총 O(2^N x N x K) 이 되겠다.

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, k;
vector<string>a;

//dp[i][j] : 특정 비트로 구성된 수들 중 k로 나눈 나머지가 j인 경우의 수
ll dp[1<<15][101]; 

// 각 수(1개)를 k로 나눈 나머지
ll remd[20];

// 비트로 구성된 수들을 k로 나눈 나머지
ll lenRem[51];

//x를 k로 나눈 나머지 반환
int rem(string x) {
	int tmp = 0;
	for (int i = 0; i < x.size(); i++) {
		tmp *= 10;
		tmp += x[i] - '0';
		tmp %= k;
	}
	return tmp;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		string x; cin >> x;
		a.push_back(x);
	}
	cin >> k;
	
	//나머지 전처리
	for (int i = 0; i < n; i++) {
		remd[i] = rem(a[i]);
	}
	lenRem[0] = 1 % k;
	for (int i = 1; i <= 50; i++) {
		lenRem[i] = (lenRem[i - 1] * 10) % k;
	}
	dp[0][0] = 1;
	//비트 순회
	for (int num = 0; num < (1 << n); num++) {
		//하나씩 수를 고른다
		for (int i = 0; i < n; i++) {
			//현재 비트에 갖고 있지 않은 수이면
			if ((num & (1 << i)) == 0) {
				int next = (num | (1 << i));
				//해당 비트 나머지 검사
				for (int j = 0; j < k; j++) {
					int nextRem = ((j * lenRem[a[i].size()]) % k + remd[i]) % k;
					dp[next][nextRem] += dp[num][j];
				}
			}
		}
	}

	ll bunza = 1, bunmo = 1;

	for (int i = 1; i <= n; i++) bunmo *= i;
	bunza = dp[(1 << n) - 1][0];
	ll gcdNum = gcd(bunza, bunmo);
	cout << bunza / gcdNum << "/" << bunmo / gcdNum << "\n";
	return 0;
}

 

 

 

 

 

 

2. 백준 2240 자두나무(Silver 1 - DP 문제)

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

2240번: 자두나무

 

풀이

DP는 모든 경우의 수를 확인할 수 있어야하므로

1. 1번 나무와 2번 나무중 어디 나무에 있을 것인지(코드에서 1번 나무는 0, 2번 나무는 1로 설정)

2. 몇 초의 시간이 흘렀는지

3. 이동 횟수가 몇 번인지

이 세가지에 따라 답이 바뀌므로 DP배열을 dp[2][1001][31]로 선언을 해준다.

 

문제에서 자두(사람)가 1번 자두 나무에 있으므로 만약 처음 자두(과일)가 2번 나무에서 떨어질 때, 자두(사람)는 한 번 이동을 해야한다.

어느 자두 나무에 떨어질지 입력 받는 배열을 time[i]라고 할 때, 1초에 떨어지는 자두 나무의 번호는 time[1]이 될 것이다.

 

time[1] = 1일 때(1초 후, 1번 자두나무에서 자두가 떨어질 때)

자두는 1번 나무에서 시작하므로 가만히 있는 방법인 dp[0][1][0] = 1

time[1] = 2일 때(1초 후, 2번 자두나무에서 자두가 떨어질 때) 

자두는 1번 나무에서 시작하므로 한 번 이동해야한다. dp[1][1][1] = 1

 

이제 그 이후에는

dp[0][i][j] = max(dp[0][i-1][j], dp[1][i-1][j-1]) # 첫번째 값: 가만히 있음, 두번째 값: 옆으로 움직임

dp[1][i][j] = max(dp[1][i-1][j], dp[0][i-1][j-1])

을 해주고 time[i]값에 따라 dp[0][i][j]+=1 이나 dp[1][i][j]+=1을 해주면 된다.

 

마지막으로 답을 구할 때는 제일 마지막 시간때 몇 번 움직여서 자두를 얼마나 먹었는지 확인하면 되므로 ans = max(ans, max(dp[0][t][i], dp[1][t][i])) 로 최댓값을 구해주면 된다.

코드

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1001;

int main()
{
	int t,w;
	cin >> t >> w;

	ll time[N] = { 0, };
	for (int i = 1; i <= t; i++) cin >> time[i];

	ll dp[2][N][31] = { 0, };
	if (time[1] == 1) dp[0][1][0] = 1;
	else dp[1][1][1] = 1;

	for (int i = 2; i <= t; i++) {
		for (int j = 0; j <= min(i,w); j++) {
			dp[0][i][j] = dp[0][i - 1][j];
			dp[1][i][j] = dp[1][i - 1][j];
			if (j > 0) {
				dp[0][i][j] = max(dp[0][i][j], dp[1][i - 1][j - 1]);
				dp[1][i][j] = max(dp[1][i][j], dp[0][i - 1][j - 1]);
			}
			dp[time[i] - 1][i][j]++;
		}
	}

	ll ans = 0;
	for (int i = 0; i <= w; i++)ans = max(ans, max(dp[0][t][i], dp[1][t][i]));

	cout << ans;
}

 

3. 백준 1014번 컨닝 (Platinum IV - bitmask dp 문제)

 

 

문제 링크 : https://www.acmicpc.net/problem/1014

 

문제

 

N행 M열 크기의 직사각형 교실이 주어지고, 각 교실은 1x1 단위 정사각형으로 이루어져 있다.

컨닝을 방지하기 위해 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위에 다른 학생이 없도록 자리배치를 하고자 할 때, 교실에 배치할 수 있는 최대 학생 수를 구하여라.

 

풀이

 

문제를 보고, 가장 먼저 든 생각은 "다 해볼 수 있는 가?"였다.

물론 최대 10x10 정사각형의 교실이 주어지면, 각 교실 자리는 100개이고, 모든 경우의 수를 다 해보는 것은

2^100 이므로 당연히 불가능하다.

 

하지만, 이 문제의 경우 i번 째 줄이 어떤 상태이고, 이 상태 배치의 경우 최대 학생 수를 알 수 있다면

i+1번째 줄을 구성하는 데에는 i번 째 줄만 신경 쓰면 된다. 그 위에 줄은 어차피 컨닝할 수 없기 때문이다.

 

따라서 모든 경우의 수를 볼 필요 없이, 그 현재 열과 윗 열의 배치만 컨닝을 하지 못하게 맞추면 되고, 그렇게 맞추면 다음엔 아래 열로 내려가 똑같이 맞추면 된다.

이 경우 비트 필드를 이용하면 가로길이가 최대 10이므로 O(2^10^2)로 "다 해볼 수 있다"

 

요약하자면, 전체 문제를 부분 문제의 구성으로 풀어냈고, 비트 필드를 이용하였기 때문에 문제 유형은 비트 필드를 이용한 다이내믹 프로그래밍이다.

dp table 구성은 이러하다.

 

dp[row][state] = 현재 row행이 state 상태일 경우, 배치할 수 있는 최대 학생 수

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int dp[11][(1 << 10)]; //dp[row][state] : row행에 state일 때 최대 학생의 수
string arr[11];
string state[(1 << 10)];
int n, m;

string ret_bin(int x) {
	string tmp = "";
	while (x) {
		if (x % 2 == 0) tmp += '0';
		else tmp += '1';
		x /= 2;
	}
	while (tmp.size() < m) tmp += '0';
	reverse(tmp.begin(), tmp.end());
	return tmp;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	

	int t; cin >> t;
	while (t--) {
		memset(dp, 0, sizeof(dp));

		cin >> n >> m;
		for (int i = 0; i < (1 << m); i++) {
			state[i] = ret_bin(i);
		}
		for (int i = 0; i < n; i++) cin >> arr[i];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < (1 << m); j++) {
				//행 체크
				string bin_str = state[j];
				bool flag = false; int cnt = 0;
				for (int a = 0; a < bin_str.size(); a++) {
					if (bin_str[a] == '1' && arr[i][a] == 'x') {
						flag = true;
						break;
					}
					if (bin_str[a] == '1' && a < bin_str.size() - 1) {
						if (bin_str[a + 1] == '1') {
							flag = true;
							break;
						}
					}
					if (bin_str[a] == '1') cnt++;
				}
				if (flag) continue;

				if (i == 0) {
					dp[i][j] = cnt;
					continue;
				}

				//윗 행 체크
				for (int k = 0; k < (1 << m); k++) {
					string up_str = state[k]; // 윗 행
					if (dp[i - 1][k] == 0) continue; //불가능한 배열이라면 pass
					flag = false;
					for (int a = 0; a < bin_str.size(); a++) {
						if (bin_str[a] == '1') {
							if (a > 0 && up_str[a - 1] == '1') {
								flag = true;
								break;
							}
							if (a < bin_str.size() - 1 && up_str[a + 1] == '1') {
								flag = true;
								break;
							}
						}
					}
					if (flag) continue;
					dp[i][j] = max(dp[i][j], cnt + dp[i - 1][k]);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < (1 << m); i++) {
			ans = max(ans, dp[n - 1][i]);
		}
		cout << ans << "\n";
	}
	return 0;
}