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

문제 1041번: 주사위

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+        

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

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

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

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

입력

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

출력

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

문제분석

문제 요구사항

• 정육면체는 한변이 N개의 주사위로 이루어져 있다. → 정육면체를 구성하는 주사위가 보이는 면에 따라서 주사위를 구분 한 후, 각 주사위가 보이는 면에 따른 최소값을 구한다.

주사위의 상태를 4가지로 구분 할 수 있다.

1. N = 1: 5개 면이 모두 보이는 경우
2. N >= 2: 모서리를 기준으로 3개 면이 동시에 보이는 상태
3. N >= 2: 주사위의 선을 기준으로 2개의 면이 동시에 보이는경우
4. N >= 2: 주사위의 1개의 면만 보이는 경우

각 상태를 기준으로 최소가 되는 값을 계산 한 후 더해주면 된다.

1. 1번 상태는 N = 1임으로 1개 뿐이다.
2. 2번 상태는 주사위가 N에 상관없이 4개 이다.
3. 3번 상태는 8N - 12개 이다.
4. 4번 상태는 5(N-2)(N-2) + 4(N-2)개 이다.

구현

2, 3,번에서 나올 수 있는 조합들을 미리 계산 해둔 후, 최솟값을 구해둔 갯수에 따라서 더해준다.

코드

// BOJ 1041 https://www.acmicpc.net/problem/6549
#include <algorithm>
#include <iostream>
#include <numeric>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  long long N;
  std::cin >> N;

  int arr[6];
  for (int i = 0; i < 6; ++i) {
    std::cin >> arr[i];
  }

  const int corner[8] = {arr[0] + arr[1] + arr[2], arr[0] + arr[1] + arr[3],
                         arr[0] + arr[2] + arr[4], arr[0] + arr[3] + arr[4],
                         arr[1] + arr[2] + arr[5], arr[1] + arr[3] + arr[5],
                         arr[2] + arr[4] + arr[5], arr[3] + arr[4] + arr[5]};
  const int min_corner = *std::min_element(corner, corner + 8);

  const int line[12] = {arr[0] + arr[1], arr[0] + arr[2], arr[0] + arr[3],
                        arr[0] + arr[4], arr[1] + arr[2], arr[1] + arr[3],
                        arr[1] + arr[5], arr[2] + arr[4], arr[2] + arr[5],
                        arr[3] + arr[4], arr[3] + arr[5], arr[4] + arr[5]};

  const int min_line = *std::min_element(line, line + 12);

  const int min_surface = *std::min_element(arr, arr + 6);

  long long ans = 0;
  if (N == 1) {
    ans = std::accumulate(arr, arr + 6, 0) - *std::max_element(arr, arr + 6);
  } else {
    ans = 4 * min_corner + (8 * N - 12) * min_line +
          (5 * N - 6) * (N - 2) * min_surface;
  }

  std::cout << ans;

  return 0;
}