#1041 주사위(simple Implement)

이번 문제는 정육면체에 대한 기하학적 구조를 상상할 수 있으면 쉽게 풀 수 있는 문제입니다.  그래서인지 난이도도 상당히 낮습니다.  난이도는 Silver III 입니다.  Bronze 난이도에 비해서는 어렵다고 할 수 있겠지만요.  현재 시점에서 정답비율은 22.6%로 낮습니다.  정답자도 531명이고요.

 

주사위를 \(N^3\) 이용해서 변마다 N개의 주사위가 위치하도록 정육면체를 만들었을 때, 주사위의 눈의 갯수의 합을 최소로 할 때, 그 값을 구하는 것입니다.

 

Dices

 

문제의 링크는 다음과 같습니다.

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

1041번: 주사위

 

전 이 문제를 N이 1일 때와 아닐 때로 나누어서 구했습니다.  N이 1일 때에는 주사위의 5면이 보이기 때문에 가장 큰 숫자를 바닥으로 놓으면 됩니다.  N이 2 이상일 때에는 다음과 같이 정리할 수 있습니다.

 

보이는 주사위 면	주사위 갯수
3	4
2	\(8N-12\)
1	\(5N^2 -16N + 12\)

 

이 테이블만 구하면 이 문제는 크게 어렵지는 않습니다.  제가 N이 1일때와 아닐때로 나눈 이유는 \(N \ge 2\)일 때만 위의 테이블이 적용되기 때문입니다.

 

아래는 여러가지 입력에 대한 답입니다.

Input1:
1
1 2 3 4 5 6

15

Input2:
2
1 3 5 7 9 11

52

Input3:
987654
31 33 35 37 39 41

151196381478444

 

주의하실 점은 입력의 숫자가 크기때문에 long long 자료형을 사용하셔야 한다는 것입니다.

예외처리할 것이 많지는 않습니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1041 - Dice
//    - by Aubrey Choi
//    - created at 2019-12-06
//------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, v[6], i, j, sum=0, max=0, min=200, min2=200, min3=200;
  scanf("%d",&n);
  for(i=0;i<6;i++) scanf("%d",v+i);
  for(i=0;i<6;i++) sum+=v[i], max=v[i]>max?v[i]:max, min=v[i]<min?v[i]:min;
  if(n==1) { printf("%d\n", sum-max); return 0; }
  int p3[8][3] = { 0,1,2, 0,2,4, 0,3,4, 0,1,3, 1,2,5, 1,3,5, 2,4,5, 3,4,5 };
  int p2[12][2] = { 0,1, 0,2, 0,3, 0,4, 1,2, 1,3, 1,5, 2,4, 2,5, 3,4, 3,5, 4,5 };
  for(i=0;i<8;i++)
  {
    for(j=0,sum=0;j<3;j++) sum+=v[p3[i][j]];
    if(sum<min3) min3=sum;
  }
  for(i=0;i<12;i++)
  {
    for(j=0,sum=0;j<2;j++) sum+=v[p2[i][j]];
    if(sum<min2) min2=sum;
  }
  printf("%lld\n", 4*min3+(8LL*n-12)*min2+(5LL*n*n-16*n+12)*min);
}