BOJ 1041 주사위(C++)

주사위 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	547	109	100	22.989%

문제

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 숫자가 써있다. 위의 전개도를 숫자가 밖으로 나오게 접는다.

A와 F에 써있는 숫자가 주어진다.

지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만드려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 써 있는 숫자가 주어질 때, 보이는 5개의 면에 써 있는 숫자의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 

2
1 2 3 4 5 6

예제 출력 

36

힌트

#include    <cstdio>
#pragma warning(disable : 4996)
#define min2(x,y) ((x) > (y) ? (y) : (x))
#define min4(w,x,y,z) (min2(w,x) < min2(y,z) ? min2(w,x) : min2(y,z))
int main()
{
    int N;
    int d[6], dd[6];
    scanf("%d", &N);
    scanf("%d%d%d%d%d%d", &d[0], &d[1], &d[2], &d[3], &d[4], &d[5]);
    if (N == 1)
    {
        int max = 0;
        int locM = 0;
        for (int i = 0; i < 6; ++i)
        {
            if (max < d[i])
            {
                max = d[i];
            }
        }
        printf("%d", d[0] + d[1] + d[2] + d[3] + d[4] + d[5] - max);
        return 0;
    }
    dd[0] = 5;  dd[1] = 4;  dd[2] = 3;  dd[3] = 2;  dd[4] = 1;  dd[5] = 0;
    int loc1;
    int min = 100;
    for (int i = 0; i < 6; ++i)
    if (d[i] < min)
    {
        min = d[i];
        loc1 = i;
    }
 
    int top1, top2, top3;
    top1 = min;
 
    min = 100;
    for (int i = 0; i < 6; ++i)
    {
        if (i != loc1 && i != dd[loc1])
        {
            if (min > d[i])
                min = d[i];
        }
    }
    top2 = min + top1;//6의 옆에 있는 애 중 가장 큰애 
 
    top3 = top1;
    if (loc1 == 0 || loc1 == 5)
    {
        top3 += min4((d[1] + d[2]), (d[2] + d[4]), (d[3] + d[4]), (d[1] + d[3]));
    }
    else if (loc1 == 1 || loc1 == 4)
    {
        top3 += min4((d[0] + d[2]), (d[0] + d[3]), (d[2] + d[5]), (d[3] + d[5]));
    }
    else if (loc1 == 2 || loc1 == 3)
    {
        top3 += min4((d[0] + d[1]), (d[0] + d[4]), (d[1] + d[5]), (d[4] + d[5]));
    }
    long long int res = 0;
    res += 4 * top3;
    res += (long long int)(N - 2) * (N - 2) * top1 * 5;
    res += (long long int)(N - 2) * top2 * 8;
    res += 4 * top2;
    res += (long long int)(N - 2)*top1 * 4;
 
    printf("%lld\n", res);
    return 0;
}

실제로 그려보면 더 쉽곘지만 

생각해보면 몇 가지로 나눌 수 있다. 

N = 1인 경우 아래에 가장 큰 값을 놓으면 나머지 값의 합이 답이 될 것이다. 

N = 2인 경우 이상부터는 

위쪽 모서리, 아래쪽 모서리, 모서리의 사이, 아래쪽 모서리 사이, 중앙 등으로 구분된다. 

그려보면 쉬운데 말로 설명하자니 상당히 어렵다.. 결국 말하자는 것은.. 

육면체의 꼭지점을 이루는 주사위와 선을 이루는 주사위, 면을 이루는 주사위마다 특성이 있다는 것이다.

어찌되었든 중요한것은 

1면만 나오는 경우, 2면이 나오는 경우, 3면이 나오는 경우 (N=1일 때는 5면이 나오는 경우이나 여기서는 제외) 

총 세가지 경우가 있다. 

6면체 모양이지만 간단하게 그리기 위해

한 면을 예로 본다면

2 1 1 2

1 0 0 1 

1 0 0 1

2 1 1 2

처럼 있을 때 (N=4인 경우) 

0에 해당하는 것이 면을 이루는 주사위이고 이 때 이런 면이 6개 있는 육면체인 경우 바닥에 닿는 부분을 제외한 5면이 모두 이런 형태와 동일할 것이다.

1에 해당하는 것은 선을 이루는 주사위이고 옆 면과 맞닿아 있으므로 주사위의 두 면이 바깥에 보여질 것이다. 6면체의 선은 모두 12개 이므로 12개의 선분에 있는 모든 주사위가 두 면이 바깥에 보일 것 같지만 사실 바닥에 닿은 선 4개는 그렇지 않으므로 8개의 선만 두 면이 보인다. 

2에 해당하는 것이 꼭지점을 이루는 주사위이고 꼭지점은 6면체에서 8개 있으나 위의 4개는 주사위의 3면이 보이나 아래의 4개는 바닥과 닿아 주사위의 2면만 보인다. 

이를 이용하면 어렵지 않다. 

주사위 중 가장 작은 한 수를 찾고, 붙어있는 두 개의 작은 수를 찾고, 꼭지점에 들어갈 붙어있는 세 개의 작은 수를 찾은 후에 단순히 갯수만큼 곱해주면 된다. 

각각 코드에서는 top1 top2 top3변수에 계산하여 넣었다. (for loop등을 이용한 더 스마트..한 방법도 있을 것이지만... 그냥 풀었다.)

1. 면을 이루는 주사위는 N - 2 * N - 2개가 면마다 있으므로 총 식은 (N-2)(N-2)*5*top1이 될 것이다. 

2. 선을 이루는 주사위는 선당 N - 2개씩 8개 있으므로 (N-2)*8*top2가 될 것이다. 

3. 꼭지점을 이루는 주사위는 4개 있을 것이므로 4*top3이 될 것이다.  

4. 바닥을 이루는 주사위는 두가지로 나뉜다. 

(면을 이루는 주사위는 바닥에 있으면 아에 보이지 않으므로 무시한다. )

4-1. 선을 이루는 주사위는 선당 N - 2개씩 4개 있으므로 (N-2)*4*top1이 될 것이다.(바닥은 제외하므로)

4-2. 꼭지점을 이루는 주사위는 4개 있을 것이므로 4*top2가 될 것이다.(바닥은 제외하므로)