백준 15651 - N과 M (3)

noj.am/15651

 

기본적인 백트래킹 문제이다. 이전에 공부해본 알고리즘들 외에 새로운걸 접하면서 이전에 공부했던 내용을 되짚는 것이 낫다고 생각해 백트래킹을 골라 연습삼아 풀었다.

C의 string이 Python에 비해 불편하기 때문에 비트마스킹을 이용하려 했다. 그러나 이 문제에서는 중복이 존재하고, 순서가 존재하기 때문에 적합한 풀이가 아니란 생각이 들었다. 순서가 존재하는 것은 int[7]을 만들고 배열의 합을 갖고 계산하여 중복없이 풀어낼 수 있으나, 중복이 존재하기 때문에 더하는 아이디어가 적합하지 않다고 생각했다.

그럼에도 문자열을 이용하고 싶진 않았다. Python이라면 문자열을 이용해도 되고 배열을 이용해도 되지만, C로 문자열 없이 어떤 것을 만들 수 있을까 생각하다가 10진법으로 마스킹을 시켰다.

 

문제)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

1<=M<=N<=7

풀이)

 int x를 선택한 수열로 잡았다. 예를 들어 1234567은 "1 2 3 4 5 6 7"을 선택하였다고 보는 것이다. 백트래킹의 구성은 '기저 상황'과 '순차적 재귀'라 보고 있기 때문에, 함수 f(x)를 실행하면 기저 상황에선 출력하는 함수 print()를 만들어 호출했고, 기저가 아닐 땐 for문으로 M의 범위 내에서 f(10 * x + i) 를 호출함으로써 재귀적인 상황을 만들었다.

처음에 시간 초과가 떠서 왜인지 고민했는데, print()에서 pow()를 써서 시간복잡도가 넘어간 것이었다. 그래서 배열을 하나 만들어두고 메모이제이션한 값을 가져왔다.

C 코드)

#include <stdio.h>

int n, m;
int a[8];
int ten[8]={1, (int)1e+1, (int)1e+2, (int)1e+3, (int)1e+4, (int)1e+5, (int)1e+6, (int)1e+7};

void print(int x) {
	for(int i = 0; i < m; i++) {
		printf(i<m-1?"%d ":"%d", (x%ten[m-i])/ten[m-1-i]);
	}
	printf("\n");
}

void f(int x, int cnt) {
	int result = x;
	if(cnt==m)
	{
		print(result);
		return;
	}
	for(int i = 1; i <= n; i++) {
		f(10 * x + i, cnt + 1);
	}
	
	
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		f(i, 1);
	}
}