Machineboy空
2309 : 일곱 난쟁이 - 순열과 조합 본문
https://www.acmicpc.net/problem/2309
문제 요약
9명의 난쟁이 중 7명의 진짜 난쟁이를 찾아라.
일곱 난쟁이의 키의 합은 100.
난이도
Bronze 1
풀이
- 9명의 순열(permutation)을 구해 가며 7번째까지의 합이 100인지 체크
- do-while문, next_permutation 활용
- 재귀함수로 순열 구현
- 9명 중 가짜 2명 뽑기 조합(combination)
- 중첩 for문으로 구현
REVIEW
2번 풀이로 구현했다. 가장 직관적인 풀이라고 생각하지만,
이제 do-while과 next_permutation 활용을 자유자재로 하고싶다.
재귀함수로 순열을 구현하는 방법은 완벽하게 이해하지 못했고, 실전에서 활용할 수 있을지도 의문이다.
하지만 피보나치 수열의 토끼 번식 예제와 같이 무한히 아래로 뻗어가는 증식 트리가 이미지화되어 떠오르긴 하는 수준.
문법정리
- void sort (RandomIt first, RandomIt last)
- * random iterator : 임의접근 이터레이터
- T accumulate(InputIt first, InputIt last, T init )
- * input iterator : 입력범위 이터레이터 / *init : 초기값
- bool next_permutation(BidirIt first, BidirIt last)
- *bidirit : 양방향 이터레이터
//array to pointer decay
int h[9];
sort(h,h+9);
vector<int> v;
sort(v.begin(), v.end());
//do-while , next_permutation
do{
if (accumulate(a, a + 7, 0) == 100)
break;
} while (next_permutation(a, a + 9));
- 자료구조 Pair
- pair <int,int> ret;
- ret.first, ret.second로 접근
코드
//풀이 1: 순열
#include <bits/stdc++.h>
using namespace std;
int a[9];
int main()
{
for (int i = 0; i < 9; i++)
{
cin >> a[i];
}
sort(a, a + 9);
do
{
if (accumulate(a, a + 7, 0) == 100)
break;
} while (next_permutation(a, a + 9));
for (int i = 0; i < 7; i++)
{
cout << a[i] << '\n';
}
}
#include <bits/stdc++.h>
using namespace std;
// 02. combination으로 푸는 방법
// 정상적 난쟁이 7명 뽑는 것과, 비정상적 난쟁이 2명 뽑는 것은 같음
int a[9], sum;
vector<int> v;
pair<int, int> ret; // pair자료 구조 쓴 것 나와의 차이
// 중첩 for문 생각하기
void solve(){
for(int i = 0; i <9; i++){
for(int j = 0; j < i; j++){
ir(sum-a[i]-a[j] == 0){
ret = {i,j};
return;
}
}
}
}
int main(){
ios_base::sync_with_stdio;
cin.tie(NULL); cout.tie(NULL);
for(int i = 0; i < 9; i++){
cin >> a[i]; sum += a[i];
}
solve();
for(int i = 0; i < 9; i++){
if(ret.first == i || ret.second == i) continue;
v.push_back(a[i]);
}
sort(v.begin(), v.end());
for(int i : v) cout << i << " ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
//순열 구현
//1. do while
//2. 직접 재귀함수 만드는 방법
int a[9];
int n = 9, r =7;
void solve(){
int sum = 0;
for(int i = 0; i<r; i++){
sum+=a[i];
}
if(sum==100){
sort(a,a+7);
for(int i = 0; i < r; i++) cout << a[i] << "\n";
exit(0); // return 과의 차이 : return solve함수 종료, exit main함수 종료
}
}
void print(){
for(int i = 0; i < r; i++) cout << a[i] << " ";
cout << '\n';
}
void makePermutation(int n, int r, int depth){ // 이 함수는 외우고 있어야 함.
if(r == depth){
print();// 제대로 뽑았는지 확인
solve();
return; // 재귀함수일 때 기저사례 중요!
}
for(int i = depth; i < n; i++){
swap(a[i],a[depth]);
makePermutation(n,r,depth +1);
swap(a[i], a[depth]);
}
return;
}
int main(){
for(int i = 0; i < n ; i++){
cin >> a[i];
}
makePermutation(n,r,0);
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
10808 알파벳 개수 / 1159 농구경기 - 카운팅 배열과 아스키코드 변환 (0) | 2024.01.30 |
---|---|
2979 트럭 주차 - 카운팅 배열 (0) | 2024.01.30 |
백준 랭킹 시스템 (0) | 2024.01.30 |
1월 4주차 (0) | 2024.01.25 |
1월 3주차 (0) | 2024.01.18 |