[BOJ/백준] 15652 N과 M (4)

● [문제번호 15652] N과 M (4)

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

● 알아야 할 것

: DFS (깊이 우선 탐색)

: 재귀

 

● 풀이 과정

: N과 M (2) 와 N과 M (3) 을 합친 문제 같다.

 

: N과 M (1)에서 중복가능을 위해 visited를 제거하고,

'NM함수 - for반복문 - 초기값' 을 수정하면 된다.

 

: 'NM함수 - for반복문 - 초기값' 은

num 배열의 가장 최근에 추가한 값부터 시작해야한다.

 

그런데 num배열에 아무것도 넣지 않은 경우에는 (NM함수 맨 처음 진입)

1부터 시작할 수 있도록 수정해야한다.

 

● 주의 할 것

: 'NM함수 - for반복문 - 초기값' 은 N과 M (2)와 다르게 조금 더 주의해야한다.

 

● 참고 할 것

: 15649 N과 M (1)

https://pirateturtle.tistory.com/243

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 숫자 저장
int num[9] = {0, };
int N, M;

// 재귀를 이용한 dfs
void NM(int cnt)
{
    // M개 숫자를 저장한 경우
    if(cnt == M)
    {
        // num 배열의 숫자를 순서대로 출력
        for(int i = 1; i <= M; i++)
            cout << num[i] << " ";
        cout << "\n";
        return;
    }
    
    // 계속해서 순서대로 숫자를 저장
    // 15649 N과 M(1) 의 차이점
    // → {중복 가능하므로 visited 배열 제거} + {시작 값 설정}
    int start = max(num[cnt], 1);
    for(int i = start; i <= N; i++)
    {
        // 1. num 배열에 넣고
        // 2. 재귀
        num[cnt + 1] = i;
        NM(cnt + 1);
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 처음에 num 배열에는 0개의 숫자가 저장되어 있으므로
    NM(0);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 (N과 M)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15649	N과 M (1)	https://pirateturtle.tistory.com/243
2	15650	N과 M (2)	https://pirateturtle.tistory.com/244
3	15651	N과 M (3)	https://pirateturtle.tistory.com/245
4	15652	N과 M (4)	https://pirateturtle.tistory.com/246
5	15654	N과 M (5)	https://pirateturtle.tistory.com/247
6	15655	N과 M (6)	https://pirateturtle.tistory.com/248
7	15656	N과 M (7)	https://pirateturtle.tistory.com/249
8	15657	N과 M (8)	https://pirateturtle.tistory.com/250
9	15663	N과 M (9)	https://pirateturtle.tistory.com/251
10	15664	N과 M (10)	https://pirateturtle.tistory.com/252
11	15665	N과 M (11)	https://pirateturtle.tistory.com/253
12	15666	N과 M (12)	https://pirateturtle.tistory.com/254