15651: N과 M (3)

• toc {:toc}

문제

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

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

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

풀이

중복이 가능한 가짓수를 선택하는 문제

is_used를 2차원 배열로 만들어 선택됐을 때 확인하는 배열을 추가했다.

⇒ m개의 숫자를 선택해야 할 때 1번째 숫자 선택 → fixed+1

2차원 is_used에 fixed를 사용하면서 중복을 허용하여 선택했다.

#include <bits/stdc++.h>
using namespace std;
 
// 중복을 허용하여 선택
int n, m;
int num[10];
int is_used[10][10];
int fixed=0;
 
void func(int cur, int fixed){
    if(cur == m){
        for(int i = 0; i < m; i++){
            cout << num[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++){
        if(is_used[fixed][i]) continue;
        is_used[fixed][i] = 1;
        num[cur] = i;
        func(cur+1, fixed+1);
        is_used[fixed][i] = 0;
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0,0);
    return 0;
}

정답코드

그냥 k를 올리면 중복된다. (너무 간단하다….)

사용했는지 안했는지는 중복되지 않을 때 필요한 부분

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/3220f7e9482f4564bf6d059a406fca47
#include <bits/stdc++.h>
using namespace std;
 
int n, m;
int arr[10];
 
void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }
  for(int i = 1; i <= n; i++){    
    arr[k] = i; // k번째 수를 i로 정함
    func(k+1); // 다음 수를 정하러 한 단계 더 들어감
  }
}
 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}