반응형
https://www.acmicpc.net/problem/15649
- 문제
1부터 N까지 자연수 중에서 중복 없이 M개를 고르는 수열을 찾는 문제다.
- 해설
visited를 이용해서 풀 수 있는 문제다...
음.......... 백트래킹 관련된 문제는 어떻게 설명해야 할 지 모르겠다...
- 풀이
#include <iostream>
using namespace std;
int N, M;
int arr[9];
int visited[9] = {0};
void dfs(int cnt)
{
if (cnt == M)
{
for (int i = 0; i < M; i++)
{
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= N; i++)
{
if (!visited[i])
{
visited[i] = true;
arr[cnt] = i;
dfs(cnt + 1);
visited[i] = false;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
dfs(0);
return 0;
}
- 새롭게 알게 된 점
반응형
'Algorithm > Baekjoon BOJ' 카테고리의 다른 글
[백준][C++] 15649 : N과 M (3) (0) | 2022.10.22 |
---|---|
[백준][C++] 15649 : N과 M (2) (0) | 2022.10.22 |
[백준][C++] 11051: 이항 계수 2 (0) | 2022.10.21 |
[백준][C++] 2004: 조합 0의 개수 (0) | 2022.10.21 |
[백준][C++] 3036 : 링 (0) | 2022.10.21 |