자바(백준) 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

오답 노트 & 새로 알게 된 점

해당 문제는 백트래킹을 사용하지 않아도 TLE가 나지 않을 것 같아 완전 탐색으로 풀었다. 

cannot이라는 배열을 사용하여 조합하면 안 되는 것들을 index로 하고 값을 true라고 저장해뒀다. 그래서

삼중 for문을 사용하여 가능한 경우의 수를 모두 탐색하는 중에 cannot 값이 false를 가지게 되면 ( = 조합해도 된다) result를 더해주었다.

여기서 가장 중요한 부분은 삼중 for문 안 주석문이다. 

 

---

코드

import java.io.*;
import java.util.*;
 
public class BOJ2422 {
    static int atoi(String srt){
        return Integer.parseInt(srt);
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = atoi(st.nextToken());
        int no = atoi(st.nextToken());
        int result = 0;
 
        boolean cannot[][] = new boolean[n+1][n+1];
 
        for(int i = 0; i < no; i++){
            st = new StringTokenizer(br.readLine());
            int s1 = atoi(st.nextToken());
            int s2 = atoi(st.nextToken());
            cannot[s1][s2] = cannot[s2][s1] = true; //조합하면 안되는 것들은 true
        }
 
        for(int i = 1; i <= n; i++){
            for(int j = i + 1; j <= n; j++){
                //이 아래 부분이 포인트임
                //여기서 미리 경우의 수를 좁혀서 아래 k와 비교할 떄 경우의 수를 줄여줌
                //만약 해당 코드를 입력하지 않는다면 i, j, k 세 수 중에 두 수를 비교하여 [s1][s2]의 값이
                //true인지 false인지 총 3번 비교할 걸 줄여줌.
                if(cannot[i][j] == false) {
                    for (int k = j + 1; k <= n; k++) {
                        if(cannot[i][k] == false && cannot[j][k] == false) result++;
                    }
                }
            }
        }
        System.out.println(result);
    }
}