[백준 1041번] 주사위 (C++)

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

1041번: 주사위

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int max_n;
ll sum, N;
int arr[6];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    
    for(int i=0; i<6; i++)
    {
        cin >> arr[i];
        sum+=arr[i]; //누적합
        max_n = max(max_n, arr[i]); //가장 큰 값
    }

    if(N==1) cout << sum - max_n; //N==1인 경우 예외처리
    else
    {
        sum = 0; //다시 초기화
        arr[0] = min(arr[0], arr[5]); //마주보는 A, F중 작은 값
        arr[1] = min(arr[1], arr[4]); //마주보는 B, E중 작은 값
        arr[2] = min(arr[2], arr[3]); //마주보는 D, C중 작은 값

        sort(arr, arr+3); //오름차순 정렬 

        sum += (arr[0] + arr[1] + arr[2]) * 4; //3면이 보이는 케이스
        sum += (arr[0] + arr[1]) * (4*(N-1) + 4*(N-2)); //2면이 보이는 케이스
        sum += arr[0] * ((N-2)*(N-2) + (N-1)*(N-2)*4); //1면이 보이는 케이스

        cout << sum;
    }
    
    return 0;
}

 

직접 해당 문제에 관해 그림을 그려보면 많이 도움이 되는 문제이다.

먼저 고려해야할 케이스가 다음과 같이 3가지가 있다.

<3면이 보이는 케이스>
맨 윗면 : 각 모서리(꼭짓점)

<2면이 보이는 케이스>
맨 윗면 : 각 모서리(꼭짓점)을 제외한 테두리 부분 (N>=3)
옆면 : 윗 모서리(꼭짓점)을 제외한 위+양 옆 테두리 부분 (N>=3)

<1면이 보이는 케이스>
맨 윗면 : 테두리를 제외한 가운데 부분 (N>=3)
옆면 : 위+양 옆 테두리 부분을 제외한 나머지 부분 (N>=3)

 

그리고 각 케이스에 대해 계산하다보면 다음과 같은 규칙을 찾을 수 있다.

<3면이 보이는 케이스>
맨 윗면 각 모서리(꼭짓점) 4개 고정
3면 * 4 : 12면

<2면이 보이는 케이스>
맨 윗면 : N>=3일 때부터 4개씩 추가로 늘어남 (4, 8, 12...)
(N-2)*4

옆면 기둥 : N>=3일 때부터 4개씩 추가로 늘어남 (8, 12, 16...)
(N-1)*4

-> (N-1)*4 + (N-2)*4

<1면이 보이는 케이스>
맨 윗면 : N>=3일 때부터 제곱 형태로 늘어남 (1, 3, 9...)
(N-2)*(N-2)

옆면 :  N>=3일 때부터 1*2형태 사각형이 가로세로 1씩 증가하는 형태로 늘어남 (1*2, 2*3, 3*4...)
해당 형태가 4개
(N-2)*(N-1)*4

-> (N-2)*(N-2) + (N-2)*(N-1)*4

 

다 조립된 형태를 기준으로 마주보는 형태가 3가지가 생기고, 각각에 대해 더 작은 값을 선택한다. (위 + 아래, 옆면 2)

추가적으로 이 3가지 값을 정렬하여 가장 작은 값부터 오도록 해준다.

 

3면이 보이는 케이스의 경우 위 3가지 값을 모두 사용한다.

2면이 보이는 케이스는 2가지 값만 필요하므로, 앞의 더 작은 값들 2개만 채택하여 사용한다.

1면이 보이는 케이스의 경우 1가지 값만 필요하므로, 가장 작은 값인 맨 앞의 값만 채택하여 사용한다.

 

그리고 N==1일 때 예외처리가 필요하다.

N==1인 경우에는 주사위 한개인채이고, 밑바닥면을 제외한 모든 면을 사용하게 된다.

따라서 6면의 누적합을 구하고 6면 중 가장 큰 값을 빼서 출력해주면 된다.

 

그리고 해당 문제가 연산에 따라 값이 굉장히 커지므로 (N=100만) 관련된 연산의 값을 long long으로 선언해주어야 한다.