백준 15649 풀이
간단한 수열을 만드는 문제였다.
그 중 경우의 수와 관련된 문제였고 입력에 대한 모든 경우를 처리해야는데 경우의 수가 많아질 수록 복잡해지는 것 같아 조금 헤맸다.
경우의 수 문제를 풀 때 가지치기 형태로 풀었던 것을 생각하여 트리처럼 생각하도록 했고 트리 탐색에 사용할 수 있는 dfs방식을 생각해냈다.
m번 반복하며 선택하지 않았던 수를 선택하여 배열에 저장하고 반복이 끝날때 배열의 값을 전부 출력하는 형태로 구현했다. (cnt==m)
문제 분류를 보니 백트래킹 문제였다. 백트래킹 문제는 dfs 혹은 bfs로 풀 수 있는만큼 이런 부분에 단련이 필요하다.
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int n;
int m;
bool visited[9] = { 0, };
int arr[9];
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);
int answer = 0;
cin >> n >> m;
dfs(0);
return 0;
}
Author And Source
이 문제에 관하여(백준 15649 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-15649-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)