[ 백준 3040 ] 백설 공주와 일곱 난쟁이 (C++)

백준의 백설공주와 일곱 난쟁이(3040) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

아홉 난쟁이 중에서 일곱 난쟁이를 찾아야 하는 문제이다. 아홉 개의 수 중에서 총 합이 100이 되는 일곱 개의 수를 찾아야 하는 문제이다. 과정에 맞게 문제를 해결해보자.

 

#1. 조합 구현하기

본인은 이 문제를 보고 가장 먼저 구현한 것은 "조합 구현" 이였다.

왜 조합을 구현해야할까 ?? 우리는 9개의 숫자 중에서, 적절한 7개의 숫자를 찾아서 합이 100이 되도록 만들어야 한다.

그럼 적절한 7개의 숫자를 찾을 때, 순서에 영향을 미치게 될까 ??

간단한 예를 한번 들어보자.

[ 1 , 2 , 3 , 4 , 5 ] 중에서 3개의 숫자를 다음과 같이 2가지 Case로 뽑았다고 가정해보자.

Case1 : [ 1 , 2 , 3 ]

Case2 : [ 2 , 3 , 1 ]

위의 2개는 합은 똑같이 6이 되지만, 순서는 다른 경우이다. 하지만 ! 숫자들의 합은 동일하므로 위와 같이 2개의 경우를 뽑는 것은 의미가 없다. 즉 ! 이 문제도 마찬가지로 숫자를 어떻게 뽑든 순서에 영향을 미치지 않는다.

따라서, 순열이 아닌 조합으로 구현을 할 수가 있다. 아직 조합에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 알아보기(Click) ]

 

#2. 정답 도출

조합만 구현하면 문제를 거의 해결했다고 볼 수 있다.

7개의 숫자를 조합으로 뽑는것과 동시에 그 합이 100이 된다면 해당 숫자들을 출력하면 된다.

 

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
using namespace std;
 
int Arr[10];
bool Flag;
bool Select[10];
vector<int> V;
 
void Input()
{
    for (int i = 0; i < 9; i++) cin >> Arr[i];
}
 
void DFS(int Idx, int Cnt, int Sum)
{
    if (Sum > 100) return;
    if (Cnt == 7 && Sum == 100)
    {
        for (int i = 0; i < V.size(); i++)    cout << Arr[V[i]] << endl;
        exit(0);
    }
 
    for (int i = Idx; i < 9; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(i);
        DFS(i, Cnt + 1, Sum + Arr[i]);
        V.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, 0, 0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}