[C++][BAEKJOON][수학] 1041번 주사위 문제 풀이 & 반례

[문제]

1041번: 주사위

[풀이]

N이 1일 때, N이 2일 때, N이 3일 때를 손으로 그려보며 규칙을 찾았다. 아래 그림 참조.

즉, N이 1일 때는 가장 큰 값을 제외하고 5개를 더해주면 되고,

N이 1보다 클 때는 다음과 같은 공식이 있었다.

 

- 면이 3개 보이는 주사위 개수: 4

- 면이 2개 보이는 주사위 개수: (N-1)*4 + (N-2)*4

- 면이 1개 보이는 주사위 개수: (N-2)*(N-2) + (N-2)*(N-1)*4 

 

공식을 구해서 풀었는데 계속 틀렸습니다가 떴다. 원인을 찾아보니 주사위를 무작정 오름차순 정렬한게 잘못됐었다.

 

즉, 주사위 값은 A B C D E F 로 순서대로 주어지고 문제에서 평면도 처럼 배치된다. 이 때, 마주보는 변(A-F, B-E, C-D)이 생겨서 작은합2개, 작은합3개는 단순히 정렬로 해결되는 문제가 아니라는 것을 알 수 있다. 아래 그림 참조!!!

따라서, 1개 최소합, 2개 최소합, 3개 최소합을 따로 구하고 그 개수만큼을 곱해주면 된다.

최소합은 3중 for문으로 마주보는 면은 index를 더했을 때 5가 되므로 index1 + index2 == 5 일 때, index1 + index3 == 5 일 때, index2 + index3 == 5일 때를 제외하고 가장 작은 경우의 수를 구해주면 된다.

 

마지막으로 !!! N은 1,000,000보다 작거나 같은 자연수이므로 int형 자료형을 쓰면 안된다. 자료형은 long long 형을 써줘야 한다. 그리고 연산 중에서도 long long 형으로 바꿔서 연산을 계속해나가야 이상한 숫자가 안나온다.

 

[반례]

#예시

1 50 50 50 50 2

 

#답

608

 

- 1개 최소합: 1

- 2개 최소합: 51

- 3개 최소합: 101(53 아님!)

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long FindMinCase(int n, vector<int> &dice);

int main() {
	int n = 0;
	vector<int> dice;

	cin >> n;
	
	int num = 0;
	for (int i = 0; i < 6; i++) {
		cin >> num;
		dice.push_back(num);
	}
	//sort(dice.begin(), dice.end()); //*****주사위 값 위치가 정해져 있어서 무작정 정렬하면 안됨!!
	if (n > 1) {
		cout << FindMinCase(n, dice);//주사위 숫자가 최소로 보일 수 있는 경우 찾기
	}
	else {
		sort(dice.begin(), dice.end());
		int sum = 0;
		for (int i = 0; i < dice.size() - 1; i++) {
			sum += dice[i];
		}
		cout << sum;
	}
	return 0;
}

long long FindMinCase(int n, vector<int> &dice) {
	int sum1 = 50;//면이 1개일 때 최소합
	int sum2 = 100;//면이 2개일 때 최소합
	int sum3 = 150;//면이 3개일 때 최소합
	
	for (int i = 0; i < dice.size(); i++) {
		if (sum1 > dice[i]) sum1 = dice[i];
		for (int j = i + 1; j < dice.size(); j++) {
			if (i + j == 5) continue;//마주보는 면은 함께 구할 수 없음
			if (sum2 > dice[i] + dice[j]) sum2 = dice[i] + dice[j];
			for (int k = j + 1; k < dice.size(); k++) {
				if (j + k == 5 || i + k == 5) continue;//마주보는 면은 함께 구할 수 없음
				if (sum3 > dice[i] + dice[j] + dice[k]) sum3 = dice[i] + dice[j] + dice[k];
			}
		}
	}
	long long result = 0;
	//면1개가 보이는 개수만큼 곱해주기
	result += sum1 * ((long long)(n - 2)*(n - 2) + ((long long)(n - 2)*(n - 1) * 4));
	//면2개가 보이는 개수만큼 곱해주기
	result += sum2 * ((n - 2) * 4 + ((n - 1) * 4));
	//면3개가 보이는 개수만큼 곱해주기
	result += sum3 * 4;

	return result;
}