MODE::CREATIVE

[백준][c++] 15649번: N과 M (1) 본문

BOJ

[백준][c++] 15649번: N과 M (1)

LEE MINGYU 2024. 9. 9. 11:04

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

 

문제 해석

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 사전순으로 출력

알고리즘 분류

  • 백 트래킹

풀이

  • 재귀함수와 불리언 배열을 이용해서 해결한다
  • endl 을 사용하면 시간초과가 발생하니 주의

코드

#include <iostream>

using namespace std;


static int N,M;
static int arr[8];
static bool check[8];

void find(int len) {
    if (len == M) {
        for (int i=0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for(int i = 1; i <= N; i++) {
        if (check[i]) continue;
        check[i] = true;
        arr[len] = i;
        find(len + 1);
        check[i] = false;
    }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
    cin >> N >> M;
    find(0);
    return 0;
}

'BOJ' 카테고리의 다른 글

[백준][c++] 11727번: 2×n 타일링 2  (0) 2024.09.09
[백준][c++] 11726번: 2×n 타일링  (0) 2024.09.09
[백준][c++] 15650번: N과 M (2)  (0) 2024.09.08
[백준][c++] 15652번: N과 M (4)  (0) 2024.09.08
[백준][JAVA] 1305번: 광고  (0) 2024.06.17