백준(BaekJoon) 15650 : N 과 M (2) c++

▶문제 : 15650번: N과 M (2) (acmicpc.net)

15650번: N과 M (2)

 

▶코드 작성

#include <iostream>

int n, m;
int arr[8];

void print(int i) {//i : arr배열의 자리
    if (i == m) {//arr배열이 m개의 수를 채웠을 때 출력
        for (int j = 0; j < m; j++) {
            std::cout << arr[j] << ' ';
        }
        std::cout << std::endl;
        return;
    }
    for (int j = arr[i - 1] + 1; j <= n; j++) {//i-1 자리의 배열값보다 +1에서 n까지 반복
        arr[i] = j;//i자리에 대입
        print(i + 1);//다음 자리 값을 찾으러 재귀호출
    }
}

int main() {
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {//1부터 n까지 반복
        arr[0] = i;//맨 앞자리에 대입
        print(1);//두번째 자리부터 탐색 시작
    }
}

 

▶해석

메인 함수에서 for문을 1부터 n까지 반복하여 arr [0]에 i를 대입하고 print함수를 호출하였다.

메인 함수에서 왜 for문을 사용했는가 하면 print함수에서 아래쪽 for문을 보면 j값의 시작이 arr [i-1]+1이다.

이유는 출력 시 중복 없이 출력해야 하므로 무조건 이전 값보다 +1 이상의 값을 출력할 수밖에 없다.

 

print함수에서는 i가 arr배열의 자리, arr배열의 길이를 나타낸다.

그러므로 길이가 m인 수열을 출력해야 하니 i==m일 때 출력해준다.

 

for문으로 arr[i-1]+1 부터 n까지 반복하여 i자리에 j를 대입한 후 재귀 함수를 호출한다.

이전 값보다 +1 이상이고, 길이가 m일 때 출력되므로 중복은 일어나지 않는다.