2309 : 일곱 난쟁이 - 순열과 조합

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제 요약

9명의 난쟁이 중 7명의 진짜 난쟁이를 찾아라.

일곱 난쟁이의 키의 합은 100.

 

난이도

Bronze 1

---

풀이

1. 9명의 순열(permutation)을 구해 가며 7번째까지의 합이 100인지 체크
   • do-while문, next_permutation 활용
   • 재귀함수로 순열 구현
2. 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;

}