[Brute Force] 로마 숫자 만들기

 

 

예제 입력 1

1

예제 출력 1

4

I, V, X, L을 만들 수 있다.

예제 입력 2

2

예제 출력 2

10

2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.

예제 입력 3

10

예제 출력 3

244

 

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

16922번: 로마 숫자 만들기

 

- 그냥 N개의 각 자리수에 I, V, X, L을 선택해서 N번 재귀를 돌리면 시간 초과가 난다. (최대 N = 20이므로, 4^20)

- 따라서, I, V, X, L을 각각 몇개씩 선택할건지 골라서 4번 재귀를 돌리는 방법으로 해결했다.

- 선택한 숫자의 개수가 달라도 중복이 발생할 수 있고( V(=5) 2개로 X(10) 1개를 만들 수 있기 때문 ) 정답의 최대값이 50 x 20 = 1000이므로 1000개의 bool 배열을 만들어 중복 여부를 체크했다.

 

 

#include <stdio.h>

int N;

int numList[4] = { 1, 5, 10, 50 };
bool numCheck[1001];
int result = 0;

void go(int numCnt, int now, int sum)
{
	if (now == 4)
	{
		if (numCnt == 0)
		{
			if (numCheck[sum] == false)
			{
				numCheck[sum] = true;
				result++;
			}
			
		}
		return;
	}

	for (int i = 0; i <= numCnt; i++)
	{
		go(numCnt - i, now + 1, sum + (numList[now]*i));
	}
}

int main(void)
{
	scanf("%d", &N);

	go(N, 0, 0);

	printf("%d\n", result);

	return 0;
}