백준(BaekJoon) 15652 : N과 M (4) c++

▶문제 : 15652번: N과 M (4) (acmicpc.net)

15652번: N과 M (4)

 

▶코드 작성

#include <iostream>
using namespace std;

int n, m;
int num[8];

void print(int i) {
    if (i == m) {//m자리면 출력
        for (int j = 0; j < m; j++) cout << num[j] << ' ';
        cout << '\n';
        return;
    }

    for (int j = num[i - 1]; j <= n; j++) {//이전값과 같거나 크면 반복
        num[i] = j;//이전값과 같거나 큰 값만 대입
        print(i + 1);//다음 자리로 이동(재귀)
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {//1부터 n까지 모두 출력하도록 반복
        num[0] = i;//이전값과 비교를 위해 0번째부터 대입
        print(1);//1번째부터 재귀 시작
    }
}

 

▶해석

문제를 보면 앞에 나오는 수가 무조건 뒤에 나오는 수와 같거나 크다는 것을 알 수 있다.

따라서 num배열을 만들어 앞에 나오는 값과 비교하도록 만들었다.

맨 앞자리는 재귀 함수에서 비교할 값이 필요하므로 메인 함수에서 for문으로 i를 1부터 n까지 반복하여 num [0]에 대입하였다. 그 후  print함수를 호출하여 1번째 자리부터 재귀를 시작하였다.

 

print함수에서 아래의 for문을 보면 j가 이전값부터 n까지 반복하는 것을 볼 수 있다.

이처럼 이전값과 비교해 같거나 큰 j값만 대입하여 문제의 풀이에 맞도록 하였다.