[BOJ/2116] 주사위 쌓기, c++

www.acmicpc.net/problem/2116

2116번: 주사위 쌓기

한줄 후기 : 초등학생들이 이걸 어케 푸냐 ? 대다나다

 

주사위 n개가 주어질 때, 1~n까지 순서대로 쌓아올리는 대신 맞닿는 윗 주사위의 아랫면과 아래 주사위의 윗면 숫자가 같게끔 두어야 한다. 그리고 모든 경우 중 옆면의 숫자 합이 가장 클 때의 값을 찾으면 되는 문제이다.

 

n이 10000까지 들어오지만 봐야하는건 주사위 1~6 숫자 밖에 없기 때문에 Bruteforce로 풀어도 된다.

이걸 Bruteforce로 어떻게 풀까 생각해봤는데, 어차피 1번 주사위에서 모든게 결정된다.

1번 주사위가 윗면에 3을 두면 그 위로는 다 알아서 결정나게 된다. 따라서 1번 주사위의 윗면을 1부터 6까지 모든 숫자로 두면서 판단하면 된다.

 

옆면을 보자. 옆면은 사실 생각안해도 되는 트릭(?) 이다.

어차피 아래-위 면만 맞추면 옆면은 옆으로 돌려 돌려 내가 원하는 대로 맞출 수 있다. 따라서 옆면을 구하기 위해서는 

Greedy하게 아래,윗면에 들어가지 않는 숫자중 최댓값을 더해주면 그 경우에서 항상 최댓값이 될 것이다.

 

위-아래를 어떻게 찾으면 될까?

어차피 주사위는 6개이고, 1번(A)-6번(F)가 마주보게 되고, 2번(B)-4번(D), 3번(C)-5번(E) 가 마주 보게 된다.

front 배열에 기록해준다. front[i] = i랑 마주보고 있는 주사위 번호이다.

 

//AC
//BOJ 2116 주사위 쌓기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dice[10001][7];
int front[7];
int main(){
	int n, num;
	int ans = 0, sum = 0, maxN = 0, idx, std;
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=6; j++){
			scanf("%d", &dice[i][j]);
		}
	}
	front[1] = 6;
	front[2] = 4;
	front[3] = 5;
	front[4] = 2;
	front[5] = 3;
	front[6] = 1;  
	for(int i=1; i<=6; i++){
		sum = 0;	maxN = 0;
		// 1번 주사위에서 i번을 첫번째로 고름
		// 서로 마주 보는 위치	  1	- 6, 2-4 , 3-5
		for(int p = 1; p <= 6; p++){
			if(p != dice[1][i] && p != dice[1][front[i]]){
				maxN = max(maxN, p);
			}
		}
		sum += maxN;
		std = dice[1][i];	//1번째 top
		for(int j=2; j<=n; j++){
			maxN = 0;
			for(int x = 1; x <= 6; x++){
				if(dice[j][x] == std){
					idx = x;	//다음 주사위에서 이전 top 위치 알아내기
					break;
				}
			}
			int top = dice[j][front[idx]];	//다음 주사위에서 이전 top과 마주보고 있던 수가 top이 됨
			int bottom = std;   //다음 주사위에서 이전 top은 bottom이 됨
			for(int k=1; k<=6; k++){
				if(k != top && k != bottom)		maxN = max(maxN, k);   //옆면에 올 수 있는 수 중 가장 큰 수 고르기
			}
			sum += maxN;
			std = top;
		}
		ans = max(ans, sum);
		sum = 0; 
	}
	cout << ans;
	return 0;
}

1번 주사위에서 1~6까지 모든 숫자를 윗면에 올려두고, 아래 for문을 통해 1번의 각 윗면 숫자에 따라 주사위를 쌓아 올린다. 

std 에는 현재 top 번호를 넣어 갱신해주고, 다음 주사위에서 bottom이 std가 되면 된다.

왜냐면 현재 top에 있는 숫자는 다음 주사위에서는 무조건 bottom이 되야하니까.

1~6까지 중 top, bottom에 있지 않는 숫자 중 최댓값을 sum에 더해주고, 모든 경우에서 ans에 가장 큰 sum에 값을 넣어주면 된다.

 

재밌는 문제다.