Machineboy空
15649: N과 M(1) - 백트래킹 본문
https://www.acmicpc.net/problem/15649
문제요약
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하라!
난이도
Silver 3
풀이 포인트
- 백트래킹
REVIEW
백트래킹은 곧 dfs다.. 아직 무슨 말인지 잘 와닿지 않는다.
다시 공부해야한다.
CODE
// 백트래킹: 뒤로 다시 돌아가서 확인해본다! 역으로 돌아가본다!
// 백트래킹을 곧 dfs라고 할 수 있다!
#include <bits/stdc++.h>
using namespace std;
// 거쳐온 경로
vector<int> v;
int visited[10];
int N,M;
// 리프노드에 왔는지 체크를 phase ,단계
void f(int phase){
if(phase == M){
for(auto it:v){
cout << it <<" ";
}
cout << '\n';
return;
}
for(int i = 1; i <= N; i++){
if(visited[i]) continue;
visited[i] = 1;
v.push_back(i);
f(phase + 1);
// 다시 초기화!
v.pop_back();
visited[i] = 0;
}
}
int main(){
cin >> N>> M;
f(0);
}
'Computer > Coding Test' 카테고리의 다른 글
C++ 문법 기초다지기 예제 모음1 - 입력, 프로세싱, 출력 (1) | 2024.10.23 |
---|---|
1717: 집합의 표현 - Union-Find Tree (0) | 2024.07.22 |
입력값과 같은 구성의 수 중 가장 작은 큰 수: NextPermutation (0) | 2024.07.08 |
1813: 논리학 교수 - Ad Hoc (0) | 2024.07.02 |
프로그래머스 PCCP 역량인증 시험 후기와 반성 (0) | 2024.06.16 |