[백준 15650] N과 M (2) [C]

백준 - 15650

---

풀이

"백준 15649, N과 M (1)"를 참고해서 풀이했다.

이전 문제에서는 아래 코드와 같이 중복되는 수열을 거르기 위한 조건을 사용했다.

for (j = 0; j < depth; j++)
	if (arr[j] == i) break;

 때문에, [1, 1], [2, 2], ..과 같은 수열을 거를 수 있었다.

이번 문제에서는 이러한 수열과 더불어 [1, 2], [2, 1]과 같은 수열도 걸러야 하므로, 다음과 같이 조건을 수정하면 된다.

for (j = 0; j < depth; j++)
	if (arr[j] >= i) break; // arr[j]에 담긴 수보다 작거나 같을 경우 저장하지 않는다.

---

소스코드

#include <stdio.h>
int arr[8], N, M;
void BT(int depth){
    for (int i = 1; i <= N; i++){
        if (!depth) arr[0] = i;
        else{
            int j;
            for (j = 0; j < depth; j++)
                if (arr[j] >= i) break;
				
            if (j == depth) arr[depth] = i;
            else continue;
        }	
		
        if (depth + 1 == M){
            for (int idx = 0; idx < M; idx++)
                printf("%d ", arr[idx]);
            putchar(10);
        }else BT(depth + 1);
    }
}
int main(){
    scanf("%d %d", &N, &M);
    BT(0);
}

---

출처 및 참고자료

15650번: N과 M (2)

[백준 15649] N과 M (1) [C]