[백준 16922] 로마 숫자 만들기 C++

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

16922번: 로마 숫자 만들기

문제풀이

 

이 문제를 보자마자 자기 자신은 중복은 되지만 순서간의 중복을 허용하지 않아한다고 생각했습니다. 

 

그래서 자기 자신은 중복으로 수열이 나올 수 있지만, 순서 간에는 중복이 허용하지 않도록 프로그래밍 했습니다.

단순히 풀려고 헀는데, 아마 로마 숫자를 다 더해서 표현하는 것이기 때문에 다 더했을 때 중복이 있어서 처음 짜자마자 돌렸을 때 마지막 케이스가 정답이 안맞았습니다.

 

입력 2까지는 다 맞았지만, 입력 10에서 모두 합했을 때 중복으로 나올 수 있는 경우의 수도 체크해주어야 한다는 것을 알았습니다. 

문제의 출력에도 나와있듯이, 서로다른 수의 개수를 출력하라고 해서

Boolean으로 된 Check배열을 만들어 총 합의 나왔는지 여부에 대해 체크하고 

최초로 구한 값에 대해서는 count++;을 수행해서 개수를 카운트하도록 했습니다.

배열의 최대값은 50인 L의 문자가 최대 20개 나왔을 때를 가정해서 넉넉하게 1100을 MAX로 두어 계산했습니다.

 

#include <iostream>

using namespace std;

#define input_max 20 + 1 //입력 최대
#define check_max 1100   // 나올 수 있는 누적합의 최대
#define char_count 4     // 문자열 총 4개
int n;

int cnt;

int a[input_max];
bool check[check_max];

bool validation() {

	int sum = 0;

	for (int i = 0; i < n; i++) {

		switch (a[i])
		{

		case 1: // 1일 때 문자열 1값
			sum += 1; 
			break;
		case 2: // 2일 때 문자열 5값
			sum += 5;
			break;
		case 3: // 3일 때 문자열 10값
			sum += 10;
			break;
		case 4: // 4일 때 문자열 50 값
			sum += 50;
			break;
			
		default:
			break;
		}
	}

	if (!check[sum]) {
		check[sum] = true;
		return true;
	}

	return false;


}
void dfs(int start, int dep) {

	if (dep == n) {
		
		if (validation()) cnt++;

		return;
	}

	for (int i = start; i < char_count; i++) {

		a[dep] = i + 1;

		dfs(i, dep + 1); // 자기 자신은 중복을 허용하기 때문에 i+1이 아닌 i로 셋팅
	}
}
void solution() {

	cin >> n;

	dfs(0, 0);


	cout << cnt << '\n';
	
}


int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);
	cout.tie(0);

	solution();

	return 0;
}