[백준] 알고리즘 16922번 - 로마 숫자 만들기문제

문제

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

16922번: 로마 숫자 만들기

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n,ans;
int arr[4] = { 1,5,10,50 };
bool check[1001];
void go(int index,int sum,int cnt) {
	if (cnt == n) { 
		if (check[sum]) return; 
		check[sum] = true;
		ans++;
		return;
	}
	for (int i = index; i < 4; i++) {
		go(i,sum + arr[i], cnt + 1);
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	go(0, 0, 0);
	cout << ans;
}

해설

sum에 만들 수 있는 경우를 다 대입해볼 수 있다.

만약에 이미 만들어진 합이면 return하고, 만들지 않은 합이면 최종 정답에 개수를 더해주게됩니다.

조합과 순열을 이해하고 작성할 수 있으면 이것도 똑같이 n개중에 4개를 지지고 볶아주면 되는거기 때문에 쉽게 해결할 수 있습니다.