[완전탐색] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

[BOJ] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

📝 풀이 과정

1 ≦ N ≦ 200 범위의 아이스크림 종류 중에서 3개를 선택해야 한다.

따라서

섞어 먹으면 안되는 조합은 notGood[i][j] 배열에 저장하고
완전탐색답게 3중 for문을 사용했다.

1. 아이스크림 종류(i와 j) 2개를 먼저 선택한다.

2. i 와 j가 섞어 먹으면 안되는 조합에 포함되는지 확인한다.

   • notGood[i][j] = true인 경우 선택하지 않는다.
   • notGood[i][j] = false인 경우 선택한다.

3. 나머지 아이스크림 종류(k) 1개를 선택한다.

4. 기존에 선택한 i, j 와 현재 k가 섞어 먹으면 안되는 조합에 포함되는지 확인한다.
   i 와 j는 2번에서 섞어먹어도 되는 것으로 판단했기에
   i - k, j - k 관계만 파악하면 된다.
   i와 j 중 하나라도 k와 섞어먹으면 안되는 조합일 경우 선택하지 않는다

   • (notGood[i][k] || notGood[j][k]) == true 인 경우 선택하지 않는다.
   • (notGood[i][k] || notGood[j][k]) == false인 경우 선택한다.

👩🏻‍💻 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int N, M, answer;
    static boolean[][] notGood;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 아이스크림 종류의 수
        M = Integer.parseInt(st.nextToken()); // 섞어먹으면 안되는 조합의 개수
        notGood = new boolean[N+1][N+1];

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int ice1 = Integer.parseInt(st.nextToken());
            int ice2 = Integer.parseInt(st.nextToken());
            notGood[ice1][ice2] = true;
            notGood[ice2][ice1] = true;
        }

        answer = 0;
        solve();
        System.out.println(answer);

    }

    private static void solve(){
        for(int i = 1; i <= N - 2; i++){
            for(int j = i + 1; j <= N - 1; j++){
                if(notGood[i][j]){
                    continue;
                }

                for(int k = j + 1; k <= N; k++){
                    if(notGood[i][k] || notGood[j][k]){
                        continue;
                    }
                    answer++;
                }
            }
        }
    }
}

💡 조합으로 찾는 코드

// 조합으로 찾기
    private void solve(int count, int start) {

        if (count == 3) {
            // 선택된 맛들이 최악의 맛이 아니라면 수를 증가
            if (worstMap[tastes[0]][tastes[1]] == 0
                    && worstMap[tastes[1]][tastes[2]] == 0
                    && worstMap[tastes[0]][tastes[2]] == 0) {
                resultCount++;
            }
            return;
        }

        for (int i = start; i <= N; i++) {
            tastes[count] = i; // 맛의 정보를 저장
            find(count + 1, i + 1);
        }
    }