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

www.acmicpc.net/problem/2422

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

 

풀이

 

1) 그래프 문제를 풀때와 같이 인접행렬 map[][] 을 만든다.

2) 3중 포문으로 한방에 검사한다.

2-1) 1부터 N까지 숫자를 선택한다. -> i

2-2) i부터 N까지 숫자를 선택한다. -> j

2-3) map[i][j] = false면 j부터 N까지 숫자를 선택한다. -> k

2-4) map[i][k] = false && map[j][k] = false 이면 answer++

3) answer 출력

 

주의사항

 

1) 조합을 쓸 필요가 없다

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_S5_2422_한윤정이이탈리아에가서아이스크림을사먹는데 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,answer;
	static boolean map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new boolean[N][N];
		
		for(int i=0; i<N; i++) {
			map[i][i] = true;
		}
		for(int i=0; i<M; i++) {
			tokens = new StringTokenizer(input.readLine());
			int start = Integer.parseInt(tokens.nextToken())-1;
			int end = Integer.parseInt(tokens.nextToken())-1;
			map [start][end] = true;
			map [end][start] = true;
		}
		
//		for(boolean x[] : map) {
//			System.out.println(Arrays.toString(x));
//		}
		
		for(int i=0; i<N; i++) {
			for(int j=i; j<N; j++) {
				if(!map[i][j]) {
					for(int k=j; k<N; k++) {
						if(!map[j][k] && !map[i][k]) {
							answer++;
//							System.out.println((i+1) +" "+(j+1) +" "+(k+1));
						}
					}
				}
			}
		}
		System.out.println(answer);
		
	}

	static String src =
			"5 3\r\n" + 
			"1 2\r\n" + 
			"3 4\r\n" + 
			"1 3";
}

 

 

후기

 

처음엔 조합으로 3숫자를 뽑아서 검사하는식으로 했지만 시간초과가 났다.

아니나 다를까 조금만 생각하면 쉽게 풀수있는 방법이 있었다. 결국 솔루션을 봤지만..

하지만 아마 하루 동안 붙잡아도 떠올리지 못했을것 같다. 그 만큼 나에겐 창의력이 부족한것 같다.

부족한 창의력은 경험으로 메꿔야한다.