안 쓰던 블로그

www.acmicpc.net/problem/6603 n개 중에 6개를 뽑는 모든 경우의 수 구하기 몇개를 뽑는지 정해져 있다면 순열을 이용할 수 있다 뽑는 6개에 대해 1이라고 하고, n-6에 대해 0이라고 한 순열을 만들고 모든 순열을 돌면서 1인 경우의 값을 출력한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; while (1) { cin >> n; vector a(n), d; if (n == 0) break; for (int i = 0; i > a[i]; for (int i = 0; i < n - 6; i++) d.pu..

순열 next_permutation()과 prev_permutation() 직접 구현하기 다음 순열, 이전 순열, 모든 순열 순열 크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다 123 132 213 231 312 321 n=3인 수열은 총 6개가 있다 여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다 첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다 또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다 그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 ..