문제 링크 : https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
풀이
백트래킹을 사용한 풀이이다.
이미 특정 숫자가 배열에 들어가 있는지 arr을 순회하면서 확인하고, 들어있지 않은 숫자들만 배열에 삽입한다.
사이즈가 m이 되는 순간 지금까지 배열에 저장해 놓은 숫자들을 출력한다.
#include <iostream>
using namespace std;
int n, m;
int arr[8];
void nNm(int num, int idx){
for(int x = 0; x < idx; ++x){ // 중복 요소 검증
if(arr[x] == num) return;
}
arr[idx] = num;
if(idx == m-1){ // base condition
for(int x = 0; x < m; ++x){
cout << arr[x] << " ";
}
cout << "\n";
return;
}
for(int x = 1; x <= n; ++x){
nNm(x, idx+1);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i){
nNm(i, 0);
}
}
arr를 모두 순회하면서 사용했는지 체크하는 것은 O(n)의 시간복잡도를 가지기에 이보다 더 간단한 방식을 찾아보았다.
isUsed라는 이미 방문했는지 체크(O(1)의 시간복잡도)하는 배열을 선언하여 이를 사용하여 다시 구현해 보았다.
확실히 위의 방법보다 시간이 줄었음을 채점 시간을 통해 확인할 수 있었다.
#include <iostream>
using namespace std;
int n, m;
int arr[8];
int isUsed[9];
void nNm(int idx){
if(idx == m){ // base condition
for(int x = 0; x < m; ++x){
cout << arr[x] << " ";
}
cout << "\n";
return;
}
for(int x = 1; x <= n; ++x){ // x를 1부터 n까지 순회하며
if(!isUsed[x]){ // x가 사용되지 않았다면
arr[idx] = x; // 배열에 삽입하고
isUsed[x] = 1; // 사용되었다고 표시
nNm(idx+1); // base condition이 될때까지 백트래킹
isUsed[x] = 0; // 사용이 끝났으므로 0으로 표시
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
nNm(0);
}
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
(C++) 백준 1182번 - 부분수열의 합 (0) | 2023.04.07 |
---|---|
(C++) 백준 9663번 - N-Queen (0) | 2023.04.07 |
(C++) 백준 13549번 - 숨바꼭질 3 (0) | 2023.04.03 |
(C++) 백준 7569번 - 토마토 (0) | 2023.04.03 |
(C++) 백준 10026번 - 적록색약 (0) | 2023.04.01 |