백준 2116 <주사위쌓기>

시뮬레이션 완전 탐색 문제이다. 문제가 어렵지는 않지만 시뮬레이션을 처음 접한다면 많은 생각이 필요한 문제.

 

문제를 이해하기 위해서는 기본적으로 주사위밑면이 어떤 부분일 경우 윗면이 어떤 부분이 온다는 것을 인지해야 하는 문제이다.

이렇게 세트로 온다는 것을 잘 생각해야 한다.

 

이 문제의 시간 복잡도는 맨처음 6가지를 고르는 경우와 다음 6개 중 한 개가 정해져 있기 때문에 최대 10000개 이하이기 때문에 6*6*10000 이므로 36만이고 옆면 중 최댓값을 찾는 경우 각각 6이라고 가정하면 6*6*10000을 한 번 더 하기 때문에

대략 72만이 될것이다.

 

문제 풀이

1. 처음 시작은 6개 경우 다해봐야 함 
2. 아랫부분과 위를 제외한 최댓값을 구한다
3. 다음 함수의 매개변수에 현재 위에 올 숫자와 이때까지의 합과 현재 옆면 중 최댓값을 인자로 넘겨 전달한다.

 

계속 적으로 제기를 돌려서

next 값이 주사위 개수가 되면 값을 최댓값과 비교해서 변경해준다.

 

전체 코드

package asd;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class sad {

	static int result, n;
	static int map[][];
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][6];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 6; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < 6; i++) {
			visit=new boolean[7];
			visit[map[0][i]]=true;
			int num = i;
			int find=0;
			if (i == 0) {
				find=map[0][5];
			} else if (i == 1) {
				find=map[0][3];
			} else if (i == 2) {
				find=map[0][4];
			} else if (i == 3) {
				find=map[0][1];
			} else if (i == 4) {
				find=map[0][2];
			} else if (i == 5) {
				find=map[0][0];
			}
			visit[find]=true;
			int max=0;
			for(int j=6;j>=1;j--) {
				if(!visit[j]) {
					 max=j;
					break;
				}
			}
			next(1, find, max);

		}
		System.out.println(result);
	}

	private static void next(int next, int who, int sum) {
		// TODO Auto-generated method stub
		visit=new boolean[7];
		if(next==n) {
			result=Math.max(result,sum);
			return;
		}
		visit[who]=true;
		int k=0;
		for(int i=0;i<6;i++) {
			if(who==map[next][i]) {
				k=i;
			}
		}
		int find=0;
		if (k == 0) {
			find=map[next][5];
		} else if (k == 1) {
			find=map[next][3];
		} else if (k == 2) {
			find=map[next][4];
		} else if (k == 3) {
			find=map[next][1];
		} else if (k == 4) {
			find=map[next][2];
		} else if (k == 5) {
			find=map[next][0];
		}
		visit[find]=true;
		int max=0;
		for(int i=6;i>=1;i--) {
			if(!visit[i]) {
				 max=i;
				break;
			}
		}
		next(next+1, find, sum+ max);
	}

}