[ 백준 2422 ] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데.. (C++)

백준의 한윤정이 이탈리아에가서...(2422) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 입력으로 주어지는 전체 아이스크림 N개의 갯수에서 섞어먹으면 안되는 아이스크름 빼고 섞어 먹을 수 있는 경우의 수를 구

  하는 문제이다. 먼저 본인은 입력으로 주어지는 섞어 먹으면 안되는 아이스크림들을 표시할 수 있도록 Visit[][] 2차원 배열을

  사용하였다.

  예를 들어 1번과 2번 아이스크림 섞어 먹을 수 없다면 Visit[1][2] = true , Visit[2][1] = true로 설정해주었다.

  1번과 2번을 섞어 먹지 못한다면 2번과 1번도 섞어 먹지 못하기 때문이다.

2. 다음은 전체중에서 3개를 고르는 조합을 구하는 방식을 이용해서 풀이를 하면 된다.

   나는 조합을 체크해주기 위해서 Select[] 라는 1차원 배열을 사용했으며, 전체 아이스크림 갯수만큼 반복하면서

   선택되지 않은 아이스크림들을 앞번호 부터 차례대로 선택하며 Vector에 넣어주는 방식으로 구현하였다.

3. 조합에 대한 개념만 있다면 어렵지 않게 풀 수 있는 문제였다.

[ 조합 구현 알아보기 ]

[ 순열 구현 알아보기 ]

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 200 + 1
using namespace std;
 
int N, M, Answer;
bool Visit[MAX][MAX];
bool Select[MAX];
 
vector<int> V;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        Visit[a][b] = true;
        Visit[b][a] = true;
    }
}
 
bool CanEat()
{
    if (Visit[V.at(0)][V.at(1)] == true || Visit[V.at(1)][V.at(2)] == true || Visit[V.at(0)][V.at(2)] == true) return false;
    return true;
}
 
void Select_Icecream(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        if (CanEat() == true) Answer++;
        return;
    }
 
    for (int i = Idx; i <= N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(i);
        Select_Icecream(i, Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
void Solution()
{
    Select_Icecream(1, 0);
    cout << Answer << endl;
}
 
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;
}