본문 바로가기

■ 알고리즘 문제 풀이/BOJ

[BOJ] 백준 15651. N과 M (3)

▶문제설명

[BOJ] 백준 15651. N과 M (3)

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



▶ 설계


[문제]

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

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

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.


문제에서 N과 M (1)과 다른점은 진한 글씨로 표시된 부분 밖에 없습니다.

N과 M(1) 풀이 링크 ( https://it-earth.tistory.com/138 )


1차원 bool 배열로 중복 체크를 해주었던 부분만 제거하면 이 문제의 정답이 됩니다.



▶ 구현



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>
using namespace std;
 
void dfs(int N, int M, vector<int>& vt){
    if(vt.size() == M){
        for(int i: vt)
            cout<<i<<" ";
        cout<<"\n";
        return;
    }
 
    for(int n=1; n<=N; n++){
        vt.push_back(n);
        dfs(N,M,vt);
        vt.pop_back();
    }
}
int main(){
    int N,M;
    vector<int> vt;
    cin>>N>>M;
    dfs(N,M,vt);
    return 0;
}
cs



▶ 결과





'■ 알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글

[BOJ] 백준 15654. N과 M (5)  (0) 2020.04.27
[BOJ] 백준 15652. N과 M (4)  (0) 2020.04.26
[BOJ] 백준 15650. N과 M (2)  (0) 2020.04.24
[BOJ] 백준 15649. N과 M (1)  (0) 2020.04.24
[BOJ] 백준 1074. Z  (0) 2020.01.25