๐Ÿ• Baaaaaarking/0x0C๊ฐ• - ๋ฐฑํŠธ๋ž˜ํ‚น

[BOJ S3][C++] ๋ฐฑ์ค€ 15666๋ฒˆ : N๊ณผ M (12)

์„ ๋‹ฌ 2022. 7. 21. 19:05
๋ฐ˜์‘ํ˜•

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

 

15666๋ฒˆ: N๊ณผ M (12)

ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์ˆ˜์—ด์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ค‘๋ณต๋˜๋Š” ์ˆ˜์—ด์„ ์—ฌ๋Ÿฌ ๋ฒˆ ์ถœ๋ ฅํ•˜๋ฉด ์•ˆ๋˜๋ฉฐ, ๊ฐ ์ˆ˜์—ด์€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. ์ˆ˜์—ด์€ ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ์ถœ๋ ฅํ•ด

www.acmicpc.net

 

๋ฌธ์ œ

N๊ฐœ์˜ ์ž์—ฐ์ˆ˜์™€ ์ž์—ฐ์ˆ˜ M์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์•„๋ž˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๊ธธ์ด๊ฐ€ M์ธ ์ˆ˜์—ด์„ ๋ชจ๋‘ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

  • N๊ฐœ์˜ ์ž์—ฐ์ˆ˜ ์ค‘์—์„œ M๊ฐœ๋ฅผ ๊ณ ๋ฅธ ์ˆ˜์—ด
  • ๊ฐ™์€ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ๊ณจ๋ผ๋„ ๋œ๋‹ค.
  • ๊ณ ๋ฅธ ์ˆ˜์—ด์€ ๋น„๋‚ด๋ฆผ์ฐจ์ˆœ์ด์–ด์•ผ ํ•œ๋‹ค.
    • ๊ธธ์ด๊ฐ€ K์ธ ์ˆ˜์—ด A๊ฐ€ A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK๋ฅผ ๋งŒ์กฑํ•˜๋ฉด, ๋น„๋‚ด๋ฆผ์ฐจ์ˆœ์ด๋ผ๊ณ  ํ•œ๋‹ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N๊ณผ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 8)

๋‘˜์งธ ์ค„์— N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ์ˆ˜๋Š” 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ

ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์ˆ˜์—ด์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ค‘๋ณต๋˜๋Š” ์ˆ˜์—ด์„ ์—ฌ๋Ÿฌ ๋ฒˆ ์ถœ๋ ฅํ•˜๋ฉด ์•ˆ๋˜๋ฉฐ, ๊ฐ ์ˆ˜์—ด์€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค.

์ˆ˜์—ด์€ ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค.

 

ํ’€์ด

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m;
int input[10];  // ์ž…๋ ฅ๋ฐ›์€ ์ˆ˜์—ด
bool used[10];  // i๋ฒˆ์งธ ์ˆ˜๋ฅผ ์‚ฌ์šฉํ–ˆ๋Š”์ง€ ์—ฌ๋ถ€ (์ค‘๋ณต ๋ฐฉ์ง€)
int arr[10];  // ์ถœ๋ ฅํ•  ์ˆ˜์—ด

void recur(int k, int cur) {
    if(k == m) {
        for(int i=0; i<m; i++)
            cout << arr[i] << " ";
        cout << "\n";
        return;
    }
    
    int tmp = 0;
    for(int i=cur; i<n; i++) {
        if(tmp != input[i]) {
            arr[k] = input[i];
            tmp = arr[k];
            recur(k+1, i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    for(int i=0; i<10; i++) input[i] = 10000;
    
    cin >> n >> m;
    for(int i=0; i<n; i++)
        cin >> input[i];
    sort(begin(input), end(input));
    
    recur(0,0);
    
    return 0;
}

/*
 */

 

 

๋ฐ˜์‘ํ˜•