[백준] 1041번 - 주사위 (C언어) - [Gold5]

 

input1	output1	input2	output2	input3	output3
2 1 2 3 4 5 6	36	3 1 2 3 4 5 6	69	1000000	50 50 50 50 50 50

해당 문제는 공간 지각 능력을 갖추고 주사위가 탁자 위에 있는 경우와 마주보았을 때의 경우를 동시에 생각해낸다면 해결할 수 있는 문제이다.

 

• 마주보았을 때의 경우 1 : 마주보는 면은 포함하지 않는다.
  • A~F면이 0~5 순서로 입력된다고 가정하였을 때 
  • A와 F는 0과 5, E와 B는 1과 4, C와 D는 2와3이 마주본다.
•  주사위가 탁자 위에 있는 경우 : 면이 1개만 보이는 경우, 면이 2개 보이는 경우, 면이 3개 보이는 경우로 나뉜다.

• N = 1 인 경우
  • 탁자위에 주사위는 1개만 올라가므로 가장 최솟값을 가지는 면이 보여야 한다.
  • 면의 최솟값은 (모든 면의 총합 - 최댓값)으로 구한다.
• N >= 2 인 경우
  • 보이는 면들의 최솟값 결정
  • 면이 1개만 보이는 경우 : (5N-6)(N-2) (맨 윗면 * 각 옆면)
  • 면이 2개 보이는 경우 : 8N-12 (각 기둥의 꼭짓점을 제외한 면)
  • 면이 3개 보이는 경우 : 4 (꼭짓점)

각 면의 합의 최대는 5000 이므로 다음과 같이 설정한다. 또한 범위 제한에 의해 result 변수는 long long으로 설정한다.

int three = 5000, two = 5000, one = 5000, large = 0;
long long result = 0;

최댓값은 max 함수를 통해 정의한다.

for (int i = 0; i < 6; i++) {
        scanf("%d", &dice[i]);
        result += dice[i];
        large = max(large, dice[i]); 
    }

N = 1 인 경우 (주사위가 1개인 경우)

if (n == 1) { // 주사위가 1개인 경우
        printf("%lld", result - large);
        return 0;
    }

주사위가 마주보는 경우를 없애면서 각 면의 합의 최솟값을 찾는다.

// 마주보는 경우 없애기
    for (int i = 0; i < 6; i++) {
        one = min(one, dice[i]); // 1면 합
        for (int j = i + 1; j < 6; j++) {
            if (i + j == 5) // 마주보는 경우
                continue;
            two = min(dice[i] + dice[j], two); // 2면합
            for (int k = j + 1; k < 6; k++) {
                if (i + k == 5 || j + k == 5) // 마주보는 경우
                    continue;
                three = min(three, dice[i] + dice[j] + dice[k]); // 3면합
            }
        }
    }

도출된 one, two, three 변수를 이용해 위에서 구했던 N >= 2 인 경우에 해당하는 식을 적용한다.

 result = 0;
    result += (5 * (long long)n * n - 16 * n + 12) * one;
    result += 4 * three;
    result += (8 * n - 12) * two;
    printf("%lld", result);

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#pragma warning(disable:4996)
#define max(x,y) ((x) > (y) ? (x) : (y)) 
#define min(x,y) ((x) < (y) ? (x) : (y)) 
// 3면이 보이는 주사위 갯수, 2면이 보이는 주사위 갯수, 1면이 보이는 주사위 갯수의 합을 구하는 문제이다.
// 마주보는 면은 포함되선 안된다.
// A-F를 0-5 순서로 입력한다고 가정했을 때,
// A,F는 0과5, E,B는 1과4, C,D는 2와3이 마주본다.
int n;
int dice[6];
int three = 5000, two = 5000, one = 5000, large = 0;
long long result = 0;
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < 6; i++) {
        scanf("%d", &dice[i]);
        result += dice[i];
        large = max(large, dice[i]); 
    }

    if (n == 1) { // 주사위가 1개인 경우
        printf("%lld", result - large);
        return 0;
    }

    // 마주보는 경우 없애기
    for (int i = 0; i < 6; i++) {
        one = min(one, dice[i]); // 1면 합
        for (int j = i + 1; j < 6; j++) {
            if (i + j == 5) // 마주보는 경우
                continue;
            two = min(dice[i] + dice[j], two); // 2면합
            for (int k = j + 1; k < 6; k++) {
                if (i + k == 5 || j + k == 5) // 마주보는 경우
                    continue;
                three = min(three, dice[i] + dice[j] + dice[k]); // 3면합
            }
        }
    }

    // 3면 : 4, 2면 : 8n-12, 1면 : (5n-6)(n-2)
    result = 0;
    result += (5 * (long long)n * n - 16 * n + 12) * one;
    result += 4 * three;
    result += (8 * n - 12) * two;
    printf("%lld", result);

    return 0;
}

실행결과

CASE1	CASE2	CASE3

 

[1041번]

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

1041번: 주사위

 

[github]

https://github.com/MinWook6457/

MinWook6457 - Overview