반응형
알고리즘 분류 : 브루트 포스
N개의 숫자 중에서 M개를 뽑는 문제다. 단, 같은 수를 여러 번 뽑아도 되며, 고른 숫자는 비내림차순이어야 한다. N과 M (2) 문제의 코드에서 시작 지점을 수정하면 된다. 시작 지점은 이전에 뽑은 숫자이다. 재귀 함수 호출에 전달할 값을 사용한 숫자와 똑같이 보내면 된다.
C++ 소스코드
#include <cstdio> #include <vector> using namespace std; int n, m, x; vector<int> a; void solve(int index, int cnt) { if (cnt == m) { for (auto i : a) printf("%d ", i+1); printf("\n"); return; } for (int i=index; i<n; i++) { a.push_back(i); solve(i, cnt+1); a.pop_back(); } } int main() { scanf("%d %d", &n, &m); solve(0, 0); return 0; }
Python 3 소스코드
from sys import stdin input = stdin.readline n, m = map(int, input().split()) a = [] def solve(index, cnt): if cnt == m: print(' '.join(map(str, a))) return for i in range(index, n): a.append(i+1) solve(i, cnt+1) a.pop() solve(0, 0)
참고
반응형