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

문제

BOJ 2422 : 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - https://www.acmicpc.net/problem/2422

풀이

n개의 아이스크림 종류 중에 3종류를 뽑는다.

1. 일단 2개를 뽑은 뒤 그 2개가 어울리지 않는 조합인지 확인한다.
2. 2개가 어울리지 않는 조합이 아니면 하나를 더 뽑는다.
3. 새로 뽑은거랑 아까 뽑은 1, 2번째랑 안맞는지 확인한다.

처음에는 dfs로 nC3 조합을 만들어 풀이했는데 시간초과가 났다.. 3중 for문으로 적당하게 조건을 처리해서 풀이했다!

또한 이중 배열을 선언해서 안맞는 조합을 저장해두었다. 원래는 따로 안맞는 조합을 List로 만들어놓고 하나하나 확인했었는데 그렇게 되면 시간복잡도에 *n이 되기 때문에 제출 시 시간초과가 난다..!

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        boolean[][] pairs = new boolean[n+1][n+1];
        for(int i=0; i<m; i++){
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            pairs[a][b] = true;
            pairs[b][a] = true;
        }

        int result = 0;
        for (int i = 1; i <= n; i++) {
            for(int j=i+1; j<=n; j++){
                if(pairs[i][j]) continue; // 뽑은 2개가 안맞는 조합이면
                for (int k = j + 1; k <= n; k++) {
                    // 새로 뽑은거랑 아까 뽑은 1, 2번째랑 안맞는지 확인
                    if(!pairs[j][k] && !pairs[k][i]){ 
                        result++;
                    }
                }
            }
        }
        System.out.println(result);
    }
}

정리

✔ 알고리즘 분류 - 브루트포스 알고리즘
✔ 난이도 - ⚪ Silver 5

🤦‍♀️ 오늘의 메모

• 조합이니까 무조건 dfs라고 생각했는데, for문을 사용하는 방법도 있다는 걸 알았다. 만들어야 하는 조합의 자리수가 3이라면 O(n^3)이니까 n이 크지 않고 조건을 잘 처리해주면 더 효율적일 수 있다는 사실!

• 참고로 조합의 시간복잡도는 O(n!)이다.

참고 사이트

https://naivep.tistory.com/81