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

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

 

이 문제는 브루트 포스 문제다. 다만 현재는 반복문을 활용해 문제를 해결했다.

 

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

bool check[2500];
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int N;
  cin >> N;

  for(int i = 0; i<=N;i++) {
    for(int j = 0;j<=N-i;j++) {
      for(int k = 0;k<=N-i-j;k++) {
        int l = N-i-j-k;
        int sum = i + j*5 + k*10 + l*50;
        check[sum] = true; 
      }
    }
  }
  int ans = 0;
  for(int i = 0; i< sizeof(check);i++) {
    if (check[i]) {
      ans++;
    }
  }
  
  cout << ans << "\n";


} 

 

 

#include <iostream>
#include <vector>

using namespace std;

vector<bool> visited(1001, false);
vector<int> selVec;
int inputN;

void myDfs(int start) {

	if ((signed)selVec.size() == 3) {	// 4등분

		int n1 = selVec[0];
		int n2 = selVec[1] - selVec[0];
		int n3 = selVec[2] - selVec[1];
		int n4 = inputN - n1 - n2 - n3;

		visited[n1 + n2 * 5 + n3 * 10 + n4 * 50] = true;
		return;

	}

	for (int i = start; i <= inputN; ++i) {
		selVec.push_back(i);
		myDfs(i);
		selVec.pop_back();
	}

}

int mySolve() {

	myDfs(0);

	int ret = 0;
	for (int i = 1; i <= 50 * inputN; ++i) {
		if (visited[i]) {
			ret += 1;
		}
	}

	return ret;

}

int main() {

	cin >> inputN;
	
	int resultVal = mySolve();
	cout << resultVal;

	return 0;
}

dfs로 푼 코드다. 연습을 더 해야겠다.