[백준 / BOJ] C++ 1041 주사위

1041번: 주사위

 

문제

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

1041번: 주사위

 

 

풀이

주사위 각 면의 숫자를 입력받고 주사위들로 N×N×N 크기의 정육면체를 만든다. 이 정육면체는 탁자 위에 있어 5면만 보이는데 이때 보이는 수들의 합의 최솟값을 구하는 문제다. '그리디하게 풀어보자' 했는데, 최대한 한 면에 작은 수를 넣고자 했고 두 면이 노출되는 경우에도 최솟값을, 세 면이 노출되는 경우에도 가능한 최솟값을 넣어줬다. 그림으로 그리다 보니 규칙을 눈치챘다.

 

주사위(A=1, B=2, C=3, D=4, E=5, F=6)

 

 

N=2일 때 정육면체를 위에서 봤을 때 전개도

예제 1번인 주사위의 A~B가  1~6일 때 N = 2인 경우를 그려봤다. N이 짝수이므로 한 쪽을 맞추면 반대쪽도 똑같을 것이다. 가장 작은 값인 1을 윗면에 배치했다. 그런 다음 1과 인접한 수들 중 가장 작은 2와 3을 인접한 위치에 배치했다. 그리고 앞면의 빈칸에 1을 놓았고 옆면을 인접하면서 가장 작은 수인 2를 배치했다. 그리고 계산을 해봤더니 예제 출력대로 나왔다.

 

N=3일 때 정육면체를 위에서 봤을 때 전개도

다음은 주사위는 같고 N=3일 때다. N=2일 때처럼 윗 면에 모두 가장 작은 수인 1을 써주었다. 그리고 각 꼭짓점은 인접하면서 합이 가장 작은 2와 3을 써주었고, 두 면이 보이는 모서리에는 1과 인접하면서 1 다음으로 작은 수인 2를 써주었다. 그리고 남은 칸들 중 두 면이 보이는 곳들은 조금 전과 같은 방식으로 1과 2를 써주었다. 이러면 남은 칸은 모두 한 면만 보이는 곳이므로 가장 작은 수인 1을 써주었다. 생각에 확신이 생긴 후 바로 코드를 작성했다.

 

처음엔 주사위의 최솟값을 찾고 그 주변 인접한 값들 중 두 수의 합이 가장 작은 두 수를 찾으려 했다. 여기서 간과한 것이 두 면이 보일 때 앞에 찾은 두 수 중 작은 값을 사용했는데 잘못 생각했었다. 왜 그랬을까. 방식을 바꿔 보이는 면의 개수마다 최솟값을 구하도록 코드를 갈아엎었다.

 

 

아무리 봐도 맞는데 '틀렸습니다'를 받아서 반례를 찾다가 N=1일 때를 고려해주지 않았음을 깨달았다.

즉, N=1일 때는 주사위의 숫자 중 최댓값을 제외한 모든 값의 합을 출력하면 되고

N ≥ 2일 때는 정육면체의 상단 꼭짓점 부분은 한 주사위의 세 면이, 그리고 꼭짓점을 제외한 모서리 부분은 한 주사위의 두 면이 보이며 나머지 칸은 모두 한 면만 보인다.

 

따라서 한 면이 보일을 때의 최솟값, 두 면이 보일 때의 최솟값, 세 면이 보일 때의 최솟값을 구한 뒤 계산해주면 된다. 최솟값을 구하는 방법은 가능한 경우가 많지 않기에 가능한 모든 경우를 배열에 넣은 후 <algorithm> 헤더파일에 있는 min_element() 함수를 사용해 줬다. min_element 함수는 vector의 iterator로 시작과 끝을 입력하면 범위 내에서 최솟값의 iterator를 반환해 준다. *(asterisk)를 함수 앞에 붙여 반환하는 iterator가 가리키는 값을 저장해 줬다.

 

세 면이 보이는 곳은 상단 꼭짓점 4개, 두 면이 보이는 곳은 상단의 네 변((n-2)×4), 옆면의 네 변((n-1)×4)이고 나머지는 한 면만 보인다. 이를 수식으로 계산해 출력해 주었다.

 

(주의) N의 범위가 1,000,000이므로 N×N만 해도 int 범위를 벗어나므로 long long을 사용해야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, a, b, c, d, e, f, ans = 0;
  cin >> n >> a >> b >> c >> d >> e >> f;
  if (n == 1) {
    vector<long long> v{a, b, c, d, e, f};
    sort(v.begin(), v.end());
    for (int i = 0; i < 5; i++)
      ans += v[i];
  } else {
    vector<long long> v{a, b, c, d, e, f};
    long long one_face = *min_element(v.begin(), v.end());
    v = {a + b, a + c, a + d, a + e, b + c, b + d, b + f, c + e, c + f, d + e, d + f, e + f};
    long long two_face = *min_element(v.begin(), v.end());
    v = {a + b + c, a + b + d, a + d + e, a + c + e, b + c + f, b + d + f, c + e + f, d + e + f};
    long long three_face = *min_element(v.begin(), v.end());
    ans += three_face * 4 + two_face * ((n - 2) * 4 + (n - 1) * 4) + one_face * ((n - 2) * (n - 2) + (n - 2) * (n - 1) * 4);
  }
  cout << ans << '\n';
  return 0;
}