작성
·
516
0
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
int cnt;
int main() {
const int r = 7;
vector<int> arr(9);
for(int i = 0; i<9; i++){
cin>> arr[i];
}
sort(arr.begin() , arr.end());
vector<bool>temp(arr.size(), 1);
for (int i = 0; i < arr.size() - r; i++) {
temp[i] = 0; // 앞에 false가 n-r개 채워지고 뒤에 true 가 r개 채워지게 하면
}
do {
cnt = 0;
for (int i = 0; i < arr.size(); i++) {
if (temp[i]) {
cnt += arr[i];
}
}
if (cnt == 100) {
for (int i = 0; i < arr.size(); i++) {
if (temp[i]) {
cout << arr[i] << "\n";
}
}
break;
}
} while (next_permutation(temp.begin(), temp.end()));
return 0;
}
그냥 순열이 아닌 조합으로 어떻게든 next_permutation을 써서 해보려고 했는데 위의 코드처럼 하면 처음에 말씀하신 9C7이 되지 않을까요..? 잘 모르겠습니다..
답변 3
1
유희준님이 너무나 잘 답변해주셨는데요. ㅎㅎ 첨언하자면 다음과 같습니다.
1
우선 강사님이 아닌데 답글을 달아서 죄송합니다
질문 하신거에 대해 제 생각을 설명하자면
모든 경우를 출력하는게 아니라 오름차순으로 정렬해서 가장 먼저 되는 한개만 출력하기 때문에
combination과 permutation의 차이가 무의미 해져 permutation으로 했다고 생각합니다.
그리고 위의 코드가 안되는 이유는
next_permutation(temp.begin(), temp.end())
에서 temp 벡터 안에 있는 값들의 순서는 변경되는데
temp벡터와 대칭되는 arr 벡터의 값들의 순서는 변경되지 않아서 값이 다르게 나오는것 같습니다.
그리고 강의에서 제공해주는 코드에서 next_permutation() 했을 때 a배열 안의 값이 어떻게 변하는지 한번 확인 하시는게 좋을것 같다고 생각합니다.
넵 답변 달아주셔서 감사합니다! 근데 제가쓴 코드 제출하면 맞았습니다! 뜨는데 맞는것 같습니다.
제가 애초에 설계할때 bool배열이랑 arr배열을 오름차순으로 했습니다.( 만약 9C2면 bool배열은 {0,0,0,0,0,0,0,1,1} 이런식으로요)
그래서 9C2의 경우, bool 배열은 밑에과정처럼 while문이 진행되는데, 1과 같은 인덱스에 대응하는 arr의 원소끼리 조합을 한것입니닷
( 2309번 출력예시를 보자면)
만약 8C2면 {0,0,0,0,0,0,0,1,1} -> 23, 25에 대응시키고
{0,0,0,0,0,0,1,0,1} -> 20,25에 대응시키고,
{0,0,0,0,0,0,1,1,0} -> 20,23에 대응시키고
이런방식으로 하면
bool 배열을 바탕으로 next_permutation을 수행해서 1이 되는 배열의 값과 대응되는 조합을 구하면 제가 짠 코드처럼 됩니다!
0
안녕하세요. 좋은 강의 항상 감사합니다.
풀이에 대해 질문있습니다!
문제에서 오름차순으로 출력하라고 했는데, 최초에 배열을 sort하긴 했지만 do-while을 순회하면서 탐색하는 배열에 요소들은 계속 섞이는데, 출력할 떄 최종적으로 오름차순으로 sort 해줘야 하지 않나요?
애초에 do-while permutation을 하는 이유가 모든 경우수를 순회하기 위함인데 이 경우에 굳이 앞에서 sort 할 필요가 있나요?
안녕하세요 코딩꾼님. 제가 교안에 permutation을 하려면 sort를 먼저 해야 된다고 명시를 해두었죠? 해당 부분 다시 읽고 오길 바라며.
코드를 한번 바꿔볼까요? 아래처럼 찍어보면 어떻게 될까요? 순열이라는 것은 순서를 바꾸긴 해도 가장 끝에서부터 바꾸는 함수 입니다.
넵 감사합니다!