2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번
www.acmicpc.net
섞으면 안되는 조합이 입력으로 주어지고 3개 조합이 가능한 방법이 몇 개 있는지 출력하는 문제입니다.
저는 섞으면 안되는 조합을 2차원배열로 표시하였습니다.
조합이 x, y로 주어지면
visit[x][y] = true;
visit[y][x] = true;
여기서 true로 표시하는 것은 x번과 y번은 섞으면 안되는 조합이라는 것입니다.
그 다음 재귀를 돌리는데 매개변수를 pre(이전에 골랐던 번호), now(방금 고른 번호), cnt(고른 갯수)로 하였고
반복문으로 마지막 고를 번호 i를 고릅니다.
i를 고를 때 첫번째로 고른 pre와 두번째로 고른 now와 섞으면 안되는 조합인지 확인한 후에 다음으로 넘겨줍니다.
마지막으로 3개를 모두 골랐으면 ans를 1 증가시킵니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static boolean noMix[][]; static int N, M, ans; static void func(int pre, int now, int cnt) { if (cnt == 3) { ans++; return; } for (int i = now + 1; i <= N; i++) { if (noMix[now][i]) continue; if (pre != -1 && noMix[pre][i]) continue; func(now, i, cnt + 1); } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); noMix = new boolean[N + 1][N + 1]; int x, y; while (M-- > 0) { st = new StringTokenizer(br.readLine()); x = Integer.parseInt(st.nextToken()); y = Integer.parseInt(st.nextToken()); noMix[x][y] = true; noMix[y][x] = true; } } public static void main(String[] args) throws Exception { input(); func(-1, 0, 0); System.out.println(ans); } } | cs |
'algorithm > Bruteforce' 카테고리의 다른 글
| boj 17281 ⚾ (0) | 2021.02.16 |
|---|---|
| boj 3040 백설 공주와 일곱 난쟁이 (0) | 2021.02.15 |
| boj 2961 도영이가 만든 맛있는 음식 (0) | 2021.02.15 |
| boj 1018 체스판 다시 칠하기 (0) | 2021.01.29 |
| boj 15686 치킨 배달 (0) | 2021.01.22 |