c언어 1041번 주사위 (백준)

#include <stdio.h>
#define min(a, b) ((a<b) ? a : b)
#define ll long long

int main(void)
{
	long long int n; 
	ll int a[7] = {0}; //주사위 면의 숫자를 입력받음
	scanf("%lld", &n);
	
	ll int max_1 = 0; //가장 큰 눈
	ll int min_1 = 0; //가장 작은 눈
	ll int sum_1 = 0; //모든 눈들의 합
	for(ll int i = 0; i<6; i++) { //눈 입력
		scanf("%lld", &a[i]);
		if(max_1 < a[i]) max_1 = a[i]; //가장 큰 눈 구하기
		if(i == 0) min_1 = a[i]; //가장 작은 눈 구하기
		if(i > 0 && min_1 > a[i]) min_1 = a[i];
		sum_1 += a[i]; //모든 눈들의 합
	}
	
	if(n==1) { //주사위가 1개면, 모든 눈의 총합에 가장 큰 눈을 빼면 됨
		printf("%lld", sum_1 - max_1);
		return 0;
	} 
	//변수들
	ll int af = min(a[0], a[5]); //면A와 면F중 더 작은 것
	ll int loop = 4; //반복을 위한 변수
	ll int index[5] = {1, 2, 3, 4}; //index 배열
	ll int jndex[5] = {2, 4, 1, 3}; //index 배열
	int i = 0; //index 변수
	ll int tmp_2 = af + a[index[i]] + a[jndex[i]]; //세 면의 눈들의 최소값 초기화
//세 면의 눈들의 최솟값 구하기		
		while(loop--) { 
			if(tmp_2 > af + a[index[i]] + a[jndex[i]]) {
			tmp_2 = af + a[index[i]] + a[jndex[i]];		
			}
			i++;
		}
	
    ll int tmp = 0; //임시 저장 변수
    ll int min_2 = a[0]+a[index[1]]; ; //두 면의 눈들의 최솟값 초기화
//두 면의 최솟값 구하기
			for(int m = 0; m<4; m++) { //면A을 포함
				tmp = a[0] + a[index[m]];
				if(min_2 > tmp) min_2 = tmp;
			}
			for(int m = 0; m<4; m++) { //면F을 포함
				tmp = a[5] + a[index[m]];
				if(min_2 > tmp) min_2 = tmp;
			}
			for(int m = 0; m<4; m++) { //면 A와 F을 포함하지 않음
				tmp = a[jndex[m]] + a[index[m]];
				if(min_2 > tmp) min_2 = tmp;
			}
		
	ll int tmp_sum = 0; //가장 작은 값을 담기 위한 변수 (정답)
	tmp_sum +=  4*tmp_2; //3면
	tmp_sum +=  4*(n-1)*min_2;//옆 부분 2면 
	if(n>2) tmp_sum += 4*(n-2)*min_2; //윗 부분 2면
	if(n>2) tmp_sum += (n-2)*(n-2)*min_1; //윗 부분 1면
	if(n>2) tmp_sum += 4*(n-1)*(n-2)*min_1; //옆 부분 1면
	
	printf("%lld", tmp_sum); //최솟값 출력
	return 0;
}

 

 

풀이

n = 1) 모든 눈의 합 - 가장 큰 눈의 합

n = 2) 세 면의 눈의 합의 최솟값 * 4 + 두 면의 눈의 합의 최솟값 * 2

n >= 3) 

윗 부분 : 세 면의 눈의 합의 최솟값 * 4

               + 두 면의 눈의 합의 최솟값 * (n-2) * 4

               + 한 면의 눈의 최솟값 * (n-2) * (n-2)

옆 부분 : 두 면의 눈의 합의 최솟값 * (n-1) * 4

               + 한 면의 눈의 최솟값 * 4 * (n-1) * (n-2) 

이다.

 

두 면, 세 면의 최솟값을 구할 땐 모든 경우의 수를 고려해서 구해야 한다.

 

예로서 세 면의 최솟값은

                 D                   3

전개도 : E A B F  -->  4  0  1  5

                 C                   2

 

A면과 F면을 기준으로 잡은 후, 이들 중 더 작은 것만을 가지고, 나머지 (B-C), (C-E), (D-B), (D-E)쌍과 비교해 본다.

 

두 면의 최솟값도 모든 경우의 수을 비교해 본다.

 

https://www.acmicpc.net/problem/1041

1041번: 주사위