문제
리뷰
오름차순 수열을 출력하되, *숫자 중복을 허용한다. *
코드
#include <iostream>
#include <algorithm>
using namespace std;
/* n과m (3)
중복 허용
1부터 n까지 자연수 중에서 m개를 고른 수열
*/
int n, m;
int arr[10]; // 출력할 수열을 담는다.
void go(int index){ // index 0부터 m-1 까지 어떤 수로 채울지 선택하는 함수
if(index == m){ // index m-1까지 모든 수를 골랐으니까 수열 출력
for(int i = 0; i < m; i++){ // 수열 출력
printf("%d ", arr[i]);
}
cout << '\n';
return;
}
for(int i = 1; i <= n; i++){ // 1부터 n까지 수를 '중복 허용'하여 선택
arr[index] = i;
go(index+1); // 다음 자리 숫자를 고르러 재귀호출
}
}
int main(void){
scanf("%d %d", &n, &m);
go(0); // 0번째 자리에 어떤 수를 넣을지 선택한다.
return 0;
} 문제
리뷰
비내림차순 수열을 출력하되, *숫자 중복을 허용한다. *
비내림차순은 '같은 숫자가 연속되거나 오름차순'이다. 예를 들어, 11223 같은 수열이 비내림차순이다.
중복 허용이니까 중복체크할 배열이 필요 없다.
코드 1
#include <iostream>
using namespace std;
/* n과m (4)
중복 허용, 비내림차순
1부터 n까지 자연수 중에서 m개를 고른 수열
*/
int n, m;
int arr[10]; // 출력할 수열을 담는다.
void go(int index, int start_num){
if(index == m){ // 수열 출력
for(int i = 0; i < m; i++){
printf("%d ", arr[i]);
}
cout << '\n';
return;
}
for(int i = start_num; i <= n; i++){ // 선택 범위의 시작 숫자만 정해준다.
arr[index] = i;
go(index+1, i); // 반드시 i 보다 큰 수부터 다시 선택해야 하는게 아니다.(비내림차순)
}
}
int main(void){
scanf("%d %d", &n, &m);
go(0, 1); // 0번째 자리에 어떤 수를 넣을지 선택한다. start는 선택범위의 시작숫자.
return 0;
} 코드 2
m 개로 이루어진 배열 arr를 채우는 '완전탐색' DFS로 풀이했다.
#include <iostream>
using namespace std;
/* n과m (4) DFS로 푼 코드
중복 허용, 비내림차순
1부터 n까지 자연수 중에서 m개를 고른 수열
*/
int n, m;
int arr[10]; // 숫자 m개를 골라 저장할 수열
void dfs(int start_num, int cnt){ // 비내림차순 이니까 start_num 활용. cnt는 선택한 숫자 개수
if(cnt == m){ // 0 ~ m-1 까지 총 m 개 선택 완료해서 수열을 출력.
for(int i = 0; i < m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
for(int i = start_num; i <= n; i++){ // 비내림차순
arr[cnt] = i; // cnt자리에 i숫자를 넣는다. 선택한 것.
dfs(i, cnt+1);
// 비내림차순이니까 i 부터 다시 선택할 수 있게 한다. 윗줄에서 선택했으니 cnt+1을 넘긴다.
}
}
int main(void){
scanf("%d %d", &n, &m);
dfs(1, 0); // 1부터 시작한다. 고른 개수.
return 0;
} 728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 부분수열의 합 백준 1182번 (0) | 2020.10.20 |
|---|---|
| 외판원순회2 백준 10971번 c++ (0) | 2020.10.20 |
| N과 M(1), (2) (0) | 2020.10.20 |
| 설탕배달 백준 2839번 (0) | 2020.10.07 |
| 분해합 백준 2231번 c++ (0) | 2020.10.07 |