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

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

์„ ๋‹ฌ 2022. 7. 13. 06:42
๋ฐ˜์‘ํ˜•

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

 

15657๋ฒˆ: N๊ณผ M (8)

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

www.acmicpc.net

 

๋ฌธ์ œ

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

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

์ž…๋ ฅ

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

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

์ถœ๋ ฅ

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

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

 

ํ’€์ด

[๐Ÿ• Baaaaaarking/0x0C๊ฐ• - ๋ฐฑํŠธ๋ž˜ํ‚น] - [BOJ S3][C++] ๋ฐฑ์ค€ 15654๋ฒˆ : N๊ณผ M (5)

 

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

https://www.acmicpc.net/problem/15654 15654๋ฒˆ: N๊ณผ M (5) N๊ฐœ์˜ ์ž์—ฐ์ˆ˜์™€ ์ž์—ฐ์ˆ˜ M์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์•„๋ž˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๊ธธ์ด๊ฐ€ M์ธ ์ˆ˜์—ด์„ ๋ชจ๋‘ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. N๊ฐœ์˜ ์ž์—ฐ์ˆ˜๋Š” ๋ชจ๋‘ ๋‹ค๋ฅธ ์ˆ˜

whkakrkr.tistory.com

์œ„ ๋ฌธ์ œ ์ฝ”๋“œ์— ์ค‘๋ณต๋งŒ ํ—ˆ์šฉํ•˜๋ฉด ๋œ๋‹ค (24๋ฒˆ์ค„)

 

// 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];
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;
    }
    
    if(cur!=0) cur--;
    for(int i=cur; i<n; i++){
        arr[k] = input[i];
        recur(k+1, i+1);
    }
}

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;
}

/*
 */
๋ฐ˜์‘ํ˜•