#include <bits/stdc++.h>
using namespace std;
int n, m;
int num[10];
int arr[10];
bool check[10];
void func(int cnt){ // 이전 수열의 마지막항과 새로 추가할 값이 같으면 중복된 수열이다.
if(cnt == m){
for(int i = 0; i < m; i++){
cout << num[i]<< ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for(int i = 0; i < n; i++){ // 선택하여 출력할 수를 num에 저장
if(!check[i] && prev_num != arr[i]){
check[i] = true;
num[cnt] = arr[i]; // cnt 번째 숫자를 i로 정한다.
prev_num = arr[i]; // 방금 선택한 수를 기억해둔다.
func(cnt+1); // 다음 숫자 탐색 시작
check[i] = false;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i <n; i++){
cin >> arr[i]; // 주어진 수를 arr에 저장
}
sort(arr, arr+n); // 정렬. 사전순으로 출력해야하기 때문.
func(0); // 0번째 수를 선택하는 것으로 시작한다
return 0;
}
리뷰
백트래킹에 익숙해지기 위한 문제 중 하나다. 수열이 [ 9, 7, 9, 1] 이 주어져도 (1, 9)를 두 번 출력하면 안된다. 하지만 (9, 9)는 출력해야 한다.
일단 수열을 입력받자마자 정렬한다. 이전 선택 값이 현재 선택 값과는 달라야 한다. 그래서 prev_num 변수를 쓴다.
처음에 prev_num 변수를 전역변수로 사용해서 틀렸다. for문 내부의 함수의 재귀호출이 끝나면 check배열을 false로 돌려놓고, 다음 i번째 숫자를 검사하게 된다. 따라서 방금 종료된 재귀 호출에서 변경된 prev_num이 그대로 적용된다는 문제가 있다. 그래서 동일한 순서(cnt)의 숫자를 선택할 때는 prev_num을 똑같이 바라봐야 한다. 따라서 지역변수로 prev_num을 써야 한다.
코드를 읽어 보면 재귀적으로 구현됬다. 이 모양은 백트래킹의 전형적인 구조니까 주석을 읽고 잘 익혀두자.
선택한 숫자를 저장하는 int arr 배열 1부터 n까지의 숫자 중에서 '선택 여부'를 저장하는 bool isused 배열 현재 몇 개의 숫자를 선택했는지 인자를 넘기는 재귀 함수 void func(int k ) 재귀 함수의 종료 조건(base condition)은 k가 m개를 모두 선택했을 때 이다.
// http://boj.kr/f36567ec0c9f44b4b460b5b29683c27b
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[10];
bool isused[10];
void func(int k){ // 현재 k개까지 수를 택했음.
if(k == m){ // m개를 모두 택했으면
for(int i = 0; i < m; i++)
cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
cout << '\n';
return;
}
for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
if(!isused[i]){ // 아직 i가 사용되지 않았으면
arr[k] = i; // k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k+1); // 다음 수를 정하러 한 단계 더 들어감. 재귀 호출이므로 새로운 스택프레임 생성됨.
isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
func함수의 for문이 핵심이다.
1부터 n까지의 수에 대해 아직 i가 사용되지 않았으면 다음 수를 정하러 한 단계 더 들어간다.
for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
if(!isused[i]){ // 아직 i가 사용되지 않았으면
arr[k] = i; // k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k+1); // 다음 수를 정하러 한 단계 더 들어감
isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
재귀로 다음 수를 정하러 함수를 호출하고 나서 종료되면, 현재 선택했던 수를 사용하지 않았다고 표시한다.
즉, 이전 단계로 돌아오는 것이다.
단 현재 값이 i인 arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없다. 어차피 자연스럽게 다른 값으로 덮힐 예정이기 때문이다.
잘 모르겠다면 함수의 중간 중간 arr, isused, k를 출력한다던가 하는 방식으로 확인하고, (영상으로도 확인)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
리뷰
재귀를 공부하면서 푼 문제다. 곱셈을 하면 int의 범위를 넘어서기 때문에 long long 을 써야 한다. 단, b승을 알려면 b/2승을 제곱하면 된다는 것을 기반으로 코드를 짜야 한다.
