BaekJoon 16922 로마 숫자 만들기

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

소스결과 1984 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 브루트포스

 

설명

I V X L 4개로 구성된 로마 숫자 N개를 이용하여 서로 만들 수 있는 다른 수의 총 가지 수를 출력하는 문제.

 

한개의 경우에 대해서 총 4개의 가지가 존재하는 전형적인 브루트 포스 문제

앞에서 미리 탐색을 한 경우에는 경우의 수에 추가 하지 않도록 확인 하는 변수가 필요하다.

또한 가지치기를 하지 않는 다면 바로 타임아웃이 걸린다. 모든 경우의 수를 다 확인 하면서 탐색을 적게 하는 방법을 적용해야 한다.

 

알고리즘

1. 숫자 n을 입력 받는다 ( 최대 깊이 )

2. 0번 인덱스 부터 앞서 선택한 값 이상인 경우를 전부 탐색한다.

3. 앞선 경우의 수에서 탐색을 하지 않았다면 경우의 수에 1을 추가한다.

4. 출력

 

소스코드

#include <iostream>

using namespace std;

const short MAX = 50 * 20;
const short value[4] = { 1 , 5, 10, 50 };

int n;
bool check[MAX + 1];
int result;

void func(int pos, int bound, int val)
{
	if (pos == n)
	{
		if (!check[val])
		{
			check[val] = true;
			++result;
		}
	}
	else
	{
		for (int i = bound; i < 4; i++)
		{
			func(pos + 1, i, val + value[i]);
		}
	}
}

int main()
{
	cin >> n;

	func(0, 0, 0);

	cout << result;

	return 0;
}