[백준 알고리즘/BOJ] 자바(java) 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

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

 

문제

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

입력

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

출력

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

 

 

 

아이스크림 종류+1만큼의 크기로 2차원 배열을 생성하고 (boolean 배열의 초기값은 false) 섞어먹으면 안되는 조합의 배열의 값을 true로 변경한다. 3중 for문을 통해 가능한 모든 아이스크림 조합을 만들고, 그 중 하나의 값이라도 true라면 continue문을 통해 개수를 증가시키지 않는다. 세 개의 값 모두 false라면 개수를 증가시킨다. 이 때 주의할 점은 아이스크림 개수(n)가 5개일 때 아이스크림 번호는 0~4가 아닌 1~5로 입력되기 때문에 배열을 [n+1][n+1]으로 생성해야 한다는 것이다. 따라서 for문에서도 n을 포함시켜야 한다.

 

package baekjoon;
import java.util.Scanner;

public class B_2422 {
	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt(); // 아이스크림 종류의 수
		int m = stdin.nextInt(); // 섞어먹으면 안되는 조합의 개수
		
		boolean array[][] = new boolean[n+1][n+1]; 
		for(int i=0;i<m;i++) {
			int a = stdin.nextInt();
			int b = stdin.nextInt();
			array[a][b] = true;
			array[b][a] = true;
		}
		stdin.close();
		
		int a = 0;
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++) 
				for(int k=j+1;k<=n;k++) {
					if(array[i][j] || array[j][k] || array[k][i])
						continue;
					a++; // 모두 false이면 a를 증가
				}
		
		System.out.println(a);
		
	}

}