알고리즘/Baekjoon

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

개발하는 크롱 2020. 11. 17. 02:48
반응형

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

1041번: 주사위

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수

www.acmicpc.net

 

주사위로 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;
}

 

반응형