[BOJ] 백준 #16922. 로마 숫자 만들기 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/16922

• 알고리즘 분류: 브루트포스
• 난이도: Silver Ⅲ

💬 풀이

문제를 읽고 고딩 때 배웠던 중복조합이 떠올랐다. 추억ㅎㅎ

처음엔 중복조합 계산값에서 중복되는 경우를 빼주면 되는 건가?라고 먼저 생각했는데, 그 대신 중복 체크용 bool배열을 이용해 중복 걱정에서 자유로울 수 있었다.

사실 for문이 삼중이나 돼서 찝찝하지만, 아직 다른 풀이는 생각이 안 난다..

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

#define MAX_VALUE 10001 // 50*20 +1

using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;

	bool* chk = new bool[MAX_VALUE] {false};
	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;
				chk[1 * i + 5 * j + 10 * k + 50 * l] = true;
			}
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < MAX_VALUE; i++) {
		if (chk[i]) { cnt++; }
	}
	cout << cnt << endl;

	return 0;
}