백준 문제 1041번 주사위 문제풀이 c++

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

1041번: 주사위

 

문제해석

 

 

이 문제는 내가 푼 방식으로 설명하기가 좀 까다로울 것 같다.

 

일단 문제에서 주어진 전개도를 잘 보아야 한다. 처음에 전개도 안보고 무지성 정렬해버리니까 틀렸었다.

전개도를 전개했을때 나오는 주사위의 모양중에 하나가 이 모양이다.

순서대로 정면에서 봤을때 , 오른쪽에서 봤을때 , 위에서 봤을때 이 3가지만 표현한것이다.

예시 그림에는 A , B , D 이지만 이걸 회전 시켰을때 나올 수있는 경우가 전부 나열하면

 

A B D

B F D

F E D

E A D

 

A E C

E F C

F B C

B A C

 

A C B

C F B

F D B

D A B

 

C B A

B D A

D E A

E C A

 

A D E

D F E

F C E

C A E

 

D B F

B C F

C E F

E D F

 

총 24가지의 경우가 있다.

 

왜 이 경우를 전부 구했냐면 인접한 3면 밖에 쓸필요가 없기 때문이다.

 

이런 4x4x4의 큐브가 있을때 겉으로 보이는 5개의 면의 합이 최소가 되려면 어떻게 해야할까?

일단 가장 작은수 부터 겉으로 보이게 끔 하는것이 최선의 방법일 것이고

정육면체에서 꼭짓점에위치한 큐브는 3개의 면이 겉으로 드러나고

모서리의 위치한 큐브는 2개의 면이 겉으로 드러나고

그 외에는 1개의 면이 겉으로 드러날것이다.

 

그렇게 배치한 모습의 형태가 아래 그림과같다.

 

각각 오른쪽 측면에서 볼때(왼쪽그림) 왼쪽 측면에서 볼때(오른쪽 그림) 뒤쪽 정면에서 볼때의 모습인데 이 상태가 합의 최소가 되는 상태로 배치하는 경우가 된다.

x의 개수는 5n^2-8n+4개

y의 개수는 8n-8개

z의 개수는 4개 이다.

 

위에서 구한 주사위의 정면 오른쪽 위쪽을 택하는 총 24 가지의 경우를 위의 식에 대입해서 24개중 최소가 되는 수가 정답이 된다.

 

아 그리고 n이 1인경우는 주사위 면을 다 더한후 6면중 가장 큰값을 바닥에 두는경우가 최소이므로 그 경우만 예외처리했다.

 

#include <iostream>
#include <algorithm>
typedef long long int ll;
using namespace std;
void f(ll X,ll Y,ll Z,ll n);
ll ans=9223372036854775807;
int a[3];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n,A,B,C,D,E,F;
    ll X,Y,Z;
    cin>>n;
    cin>>A>>B>>C>>D>>E>>F;
    if(n==1)
    {
        cout<<A+B+C+D+E+F-max({A,B,C,D,E,F});
    }
    else
    {
        a[0]=A; a[1]=B; a[2]=D;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=B; a[1]=F; a[2]=D;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=F; a[1]=E; a[2]=D;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=E; a[1]=A; a[2]=D;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        a[0]=A; a[1]=E; a[2]=C;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=E; a[1]=F; a[2]=C;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=F; a[1]=B; a[2]=C;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=B; a[1]=A; a[2]=C;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        a[0]=A; a[1]=C; a[2]=B;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=C; a[1]=F; a[2]=B;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=F; a[1]=D; a[2]=B;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=D; a[1]=A; a[2]=B;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        a[0]=C; a[1]=B; a[2]=A;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=B; a[1]=D; a[2]=A;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=D; a[1]=E; a[2]=A;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=E; a[1]=C; a[2]=A;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        a[0]=A; a[1]=D; a[2]=E;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=D; a[1]=F; a[2]=E;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=F; a[1]=C; a[2]=E;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=C; a[1]=A; a[2]=E;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        a[0]=D; a[1]=B; a[2]=F;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=B; a[1]=C; a[2]=F;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=C; a[1]=E; a[2]=F;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);
        a[0]=E; a[1]=D; a[2]=F;
        sort(a,a+3);
        X=a[0]; Y=a[1]; Z=a[2];
        f(X,Y,Z,n);

        cout<<ans;
    }
}
void f(ll X,ll Y,ll Z,ll n){
    ans=min(ans,2*X*n*n+2*(Y*2*n+X*(n*n-2*n))+Z*4+Y*(4*n-8)+X*(n-2)*(n-2));
    return;
}

2*X*n*n+2*(Y*2*n+X*(n*n-2*n))+Z*4+Y*(4*n-8)+X*(n-2)*(n-2)를 전개하면 X*(5n^2-8n+4)+Y*(8n-8)+4*Z식이 나온다.

 

그리디 문제는 설명 하는게 좀 쉽지 않은 듯하다.