[BOJ/백준][Gold5] 1041 : 주사위 (C++)

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

1041번: 주사위

 

 

[난이도] Gold5
[유형] 수학

[풀이]
정육면체는 탁자위에서 보이는 정육면체의 면은 크게 3가지로 나눌 수 있습니다.
3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분

1x1x1 짜리 주사위의 모양을 미리 알고 있으므로 위 3가지 모양의 최솟값을 미리 구해놓고
각각이 NxNxN 정육면체에 몇번 들어가는지를 구하면 됩니다.

3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분의 최솟값을 각각
p,q,r이라고 하면

p는 정육면체의 맨 위의 꼭짓점 이므로 4*p ,
q는 탁자에 붙어있는 아래의 꼭짓점 4개와 탁자에 붙어있는 모서리를 제외한 8개의 모서리에
각각 N-2개만큼 존재하므로 4*q+8*(N-2)*q ,
r은 그 이외의 모든 면이므로 4*(N-2)*r+5*(N-2)*(N-2)*r

 

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll N,a[6];
int main(){
    ll p=200,q=200,r=200;
    scanf("%lld",&N);
    for(int i=0;i<6;i++) {
        scanf("%lld",&a[i]);
        r=min(r,a[i]);
    }
    if(N==1) {
        int sum=0,m=0;
        for(int i=0;i<6;i++){
            sum+=a[i];
            m=max(m,(int)a[i]);
        }
        printf("%d",sum-m);
        return 0;
    }
    p=min(p,a[0]+a[1]+a[2]);
    p=min(p,a[0]+a[3]+a[4]);
    p=min(p,a[0]+a[1]+a[3]);
    p=min(p,a[0]+a[2]+a[4]);
    p=min(p,a[5]+a[3]+a[4]);
    p=min(p,a[5]+a[1]+a[3]);
    p=min(p,a[5]+a[1]+a[2]);
    p=min(p,a[5]+a[2]+a[4]);
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(i!=j && i+j!=5) q=min(q,a[i]+a[j]);
        }
    }
    ll ans = 4*p+4*q+8*(N-2)*q+4*(N-2)*r+5*(N-2)*(N-2)*r;
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1041.cpp