백준 1041: 주사위 (C++)

문제 링크: https://www.acmicpc.net/problem/1041

1041번: 주사위

 

주사위로 N*N*N크기의 정육면체를 만들었을 때 3면이 보이는 주사위, 2면이 보이는 주사위, 1면이 보이는 주사위의 개수를 구해서 각 개수를 3면이 보였을 때 최소 조합, 2면이 보였을 때 최소 조합, 주사위의 적힌 최소 숫자(1면이 보였을 때 최소 조합)에 곱해주면 된다.

즉 (3면 최소조합)*(3면 보이는 주사위 개수) + (2면 최소조합)*(2면 보이는 주사위 개수) +(주사위 적힌 숫자 중 최소)*(1면 보이는 주사위 개수)를 구하는 문제이다.

 

 

주사위에서 서로 마주보는 면이 함께 보여질 수 없으므로 3면 or 2면이 보이는 최소 조합에서 제외해줘야 한다.

전개도를 접어보면 A-F, B-E, C-D가 서로 마주본다.

아래 소스 코드에서는 주사위에 적힌 숫자(A-F)를 dice배열에 알파벳 순으로 입력 받았다. 따라서 마주보는 조합은 dice배열의 인덱스끼리의 합이 5가 되는 경우이다. 해당 경우를 제외한 최소 조합을 찾도록 반복문을 돌렸다.

예) A(0) + F(5) = 5(서로 마주보는 조합이므로 최소 조합에 포함시킬 수 없음)

최소조합을 찾아 각 min3(3면 최소 조합), min2(2면 최소 조합), min1(주사위 눈 중 최솟값)에 저장해줬다.

 

• 3면이 보이는 주사위 개수: 4
• 2면이 보이는 주사위 개수: 8n - 12
• 1면만 보이는 주사위 개수: 5n^2 - 16n + 12

 

 

위를 검산해봤다.

총 보이는 주사위 면의 개수(!주사위 개수) == 5 * n^2 와 위에서 구한면 개수 * 주사위 개수의 합이 맞아야한다.

3*4 + 2*(8n-12) + 5n^2 - 16n + 12 = 5n^2이므로 주사위 개수를 알맞게 구한 것을 확인할 수 있다.

 

필요한 숫자를 다 구했으니 단순히 곱하고 더해주면 된다.

 (3면 최소조합)*(3면 보이는 주사위 개수) + (2면 최소조합)*(2면 보이는 주사위 개수) +(주사위 적힌 숫자 중 최소)*(1면 보이는 주사위 개수) 를 구하면 답이 바로 나온다.

 

그러나, 어렵지 않은 문제임에 불구하고 꽤 틀렸었는데 2가지 이유가 있다.

 

 

 

1. 최대 테스트 케이스가 

1000000

50 50 50 50 50 50

으로 답 250000000000000이 나온다. 정수형 범위를 넘어가기 때문에 틀렸었다. long long으로 바꿔주고 해결했다.

 

2. 90%에서 틀렸습니다 가 떴는데 N=1일 때 처리를 안해줘서였다.

N = 1인 경우 주사위의 5면이 무조건 보인다. 가장 큰 주사위 눈의 값만 제외하고 5면의 수를 다 더한 값을 출력해줘야 한다.

위 2문제를 해결해주니 바로 통과됐다.

 

#include<cstdio>
#include<algorithm>
using namespace std;

int n;
int dice[6];
int min3 = 151, min2 = 101, min1 = 51, max1 = 0;
long long answer = 0;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < 6; i++) {
		scanf("%d", &dice[i]);
		answer += dice[i];
		max1 = max(max1, dice[i]);
	}

	if (n == 1) {
		printf("%lld", answer - max1);
		return 0;
	}

	for (int i = 0; i < 6; i++) {
		min1 = min(min1, dice[i]);
		for (int j = i + 1; j < 6; j++) {
			if (i + j == 5) {
				continue;
			}
			min2 = min(min2, dice[i] + dice[j]);
			for (int k = j + 1; k < 6; k++) {
				if (j + k == 5 || k + i == 5) {
					continue;
				}
				min3 = min(min3, dice[i] + dice[j] + dice[k]);
			}
		}
	}

	answer = 0;
	answer += (5 * (long long)n*n - 16 * n + 12) * min1;
	answer += 4 * min3;
	answer += (8 * n - 12) * min2;

	printf("%lld", answer);
	return 0;
}