PS/BOJ

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

76 2024. 2. 9. 00:19
728x90

한윤정이 이탈리아에 가서 아이스크림을 사먹는데 

1 초 128 MB 11014 4434 3345 40.306%

문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

예제 입력 1

5 3
1 2
3 4
1 3

예제 출력 1

3

힌트

5개의 아이스크림과 3가지 섞어먹으면 안 되는 조합이 있다. 1번은 2번 3번과 섞으면 안되고, 3번은 4번과 섞으면 안 된다. 따라서 (1 4 5), (2 3 5), (2 4 5)와 같이 3가지 방법이 있다.

 

 

재귀를 사용한 백트래킹 기법으로 해결이 가능한 문제다.

먼저 입력에 맞춰서 섞으면 안되는 아이스크림을 bool타입 2차원 배열의 형태로 저장한다.

예를들어 1번과 3번 아이스크림을 섞어 먹을 수 없다면, cantMix[1][3] = true;, cantMix[3][1] = true; 와 같이 2차원배열에 저장해두고 1번 아이스크림부터 N번 아이스크림까지 반복문을 돌면서 고를 수 있는 아이스크림 3개를 골라 경우의 수를 카운팅하면 된다.

 

아이스크림을 고를 수 있는지 없는지 확인하기 위해 현재까지 고른 아이스크림을 저장하기 위한 배열을 별도로 만들고, 배열에 포함된 아이스크림들(현재까지 선택한 아이스크림들)과 고르고 싶은 아이스크림을 섞을 수 있는지 비교한 후 저장한다. 이 과정을 끝까지 반복하면 선택가능한 모든 경우의 수를 계산할 수 있다.

 

위 아이디어를 코드로 옮기면 아래와 같다.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m,result = 0;
bool cantMix[201][201]; // 수의 범위가 작으므로 맵보다 배열이 유리
vector<int> selected;

/**
 * 같이 먹으면 안되는 아이스크림 조합 생성
 * 앞에서부터 아이스크림을 하나 고르고, 그 아이스크림과 함께 골라도 되는 경우만 세어서 3개 고를때까지 반복 => 숫자 세기
*/
// 몇개 골랐는지, 어떤 인덱스까지 탐색했는지(다음 인덱스부터 탐색)
void selectIce(int start){
    if(selected.size()==3){ // 3개를 골랐다면
        result++;
        return;
    }
    for(int i=start+1;i<n+1;i++){ // 1번부터 n번까지의 아이스크림에 대해
        // i번째 아이스크림을 현재 집합에 넣을 수 있는지 확인
        bool able = true; // 넣을 수 있음
        // 현재 집합에 포함된 수들과 합쳐서 넣어도 되는지 확인
        for(int j=0;j<selected.size();j++){
            if(cantMix[i][selected[j]]){ // i와 selected의 j번째 인덱스의 인자를 섞을 수 없다면
                able = false;
                break;
            }
        }
        if(able){ // 넣을수 있다면
            selected.push_back(i);
            selectIce(i);
            selected.pop_back();
        } 
    }
}


int main(){
    cin.tie(NULL) -> ios::sync_with_stdio(false);
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        // 섞어먹으면 안되는 조합들
        cantMix[a][b] = true;
        cantMix[b][a] = true;
    }
    selectIce(0); // 아이스크림 고르기
    cout<<result<<endl;
}

 

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

 

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번

www.acmicpc.net