[백준][BOJ 2422] - Ice Cream

문제

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

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

 

 

 

문제 접근

• 1부터 $N$까지의 수들 중 3개를 뽑는 경우의 수를 구하는 문제 단 제약 조건이 달려 있는데 섞어먹으면 안되는 조합이 존재한다는 것이다. 만약 1은 2와 섞일 수 없다 라고 한다면 (1, 2, X) 로 되어 있는 모든 조합은 카운팅되지 않는다는 것이다.
• 즉 3개를 뽑은 뒤 각각의 수가 섞일 수 없는 수에 포함되어 있는지를 한 번 더 체크해야 한다는 것이다.
• 이것은 각 수당 섞일 수 없는 수들을 하나의 Set으로 만들어 contains()를 통해 확인하는 형식으로 접근하였다. 해당 연산이 $O(1)$에 끝나기 때문에 더 효율적이라고 생각했기 때문이다.

 

 

풀이 코드

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

public class Main {

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    Map<Integer, Set<Integer>> map = new HashMap<>();

    for (int i = 0; i < M; i++){
      st = new StringTokenizer(br.readLine());
      int key = Integer.parseInt(st.nextToken());
      int val = Integer.parseInt(st.nextToken());

      if (!map.containsKey(key)){
        map.put(key, new HashSet<>());
      }
      map.get(key).add(val);
    }

    int ans = 0;

    for (int i = 1; i <= N - 2; i++){
      for (int j = i + 1; j <= N - 1; j++){
        for (int k = j + 1; k <= N; k++){
          if (map.containsKey(i) && (map.get(i).contains(j) || map.get(i).contains(k))){
            continue;
          }

          if (map.containsKey(j) && (map.get(j).contains(i) || map.get(j).contains(k))){
            continue;
          }

          if (map.containsKey(k) && (map.get(k).contains(i) || map.get(k).contains(j))){
            continue;
          }

          ans++;
        }
      }
    }

    System.out.println(ans);
  }
}