백준) 16922번 : 로마 숫자 만들기 in C

Problem

16922번: 로마 숫자 만들기

Solution.

 

백트레킹 기법 중 DFS 알고리즘을 사용해서 풀 수 있었다.

1, 5, 10, 50 총 4 가지 로마 숫자에 대해서 N개의 원소로 중복조합한 뒤 그 합을 구하면 된다.

중복 조합은 같은 걸 또 뽑으면서 조합할 수 있다는 뜻이다. 예를 들어 1 뽑고 또 1뽑고 해도 된다는 얘기.

 

이 문제에서 중복조합한 것의 합이 또 중복될 수 있는 게 관건이었다.

예를 들어 N이 6이라면

5, 10, 10, 10, 10, 10 = 55

1, 1, 1, 1, 1, 50 = 55

인 경우 둘 다 중복 조합 조건을 만족하지만 그 합은 중복이므로 이 둘을 따로 카운트하면 안된다는 점이다.

 

파이썬은 알아서 중복 없애주는 세트에다 집어넣고 세트 크기 구하면 좋겠지만 C언어는 상남자라서 개발자한테 알아서 하라고 시킨다.

 

어차피 중복조합으로 생길 수 있는 합의 최댓값은 50이 20개 있는 1000이니까

visited 배열을 1001까지 만들고(index 사용시 1~1000 값을 직접 사용해야 하니까 크기는 1001로 선언)

0으로 싹 다 초기화 시키고, 중복조합으로 만들어진 합(total)을 index로 사용해서 visited 됐는지 안됐는지 판단하고 카운팅했다.

 

DFS 함수 작성할 때 헷갈렸던 점이

for 문에서 i 처음 값을 0이 아니라 roman_num, 즉 이미 고려하고 있었던 로마 숫자부터 설정해야 한다는 점이었다.

나는 for문 i = 0을 초깃값으로 처음 쓰고 돌려봤는데 당연히 런타임 초과. N을 20으로 넣으면 몇 초 지나도 안나온다.

이건 내가 좀 더 생각하면 될 부분이었다. 마이 미스테이크.

 

빙 챗봇 답변.

"

조합과 중복조합의 차이를 예시를 들어 설명해 드리겠습니다. 예를 들어, {1, 2, 3}이라는 집합에서 2개의 원소를 선택하는 경우를 생각해 봅시다.

조합의 경우, 각 원소는 한 번만 선택할 수 있습니다. 따라서 가능한 조합은 다음과 같습니다: (1, 2), (1, 3), (2, 3).

반면에 중복조합의 경우, 각 원소를 여러 번 선택할 수 있습니다. 따라서 가능한 중복조합은 다음과 같습니다: (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

이처럼 조합과 중복조합의 차이는 같은 원소를 여러 번 선택할 수 있는지 여부입니다. 이해가 되셨나요?

"

즉 (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3). 이렇게 조합하지

(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). 이렇게 이미 고려한 걸 또 보지 않는다는 얘기였다.

 

그냥 조합이면 i = roman_num + 1을 초깃값으로 정하고 시작하면 될 것이다.

 

 

Code.

#include <stdio.h>

int roman[4] = {1, 5, 10, 50};
int visited[1001] = {0, };
int N;
int count = 0;

void DFS(int depth, int roman_num, int total){ // depth는 깊이, roman_num은 현재 고려하는 roman 숫자, total은 현재 로마 숫자로 만들어진 값. 
	int i;
	
	//total은 현재 고려하는 roman 숫자의 합. 
	total += roman[roman_num];
	
	if(depth == N){ // DFS의 끝, 즉 사용자로부터 받은 N 까지 total 계산 완료. 
		if(!visited[total]){ // 만약 이전에 이미 total 값에 해당하는 수를 만든 적이 없다면 count += 1 하고 visited을 1로 만들어준다. 
			visited[total] = 1;
			count++;
		}
		return;
	}
	
	for(i = roman_num; i < 4; i++){ // 중복조합이므로 i는 roman_num 부터 시작한다. 
		DFS(depth + 1, i, total);
	}
};

int main() {
	int i;
	scanf("%d", &N);
	for(i = 0; i<4; i++)
		DFS(1, i, 0);
		
	printf("%d\n", count);
	
	return 0;
}