[백준] 2116 - 주사위 쌓기 (C++)

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

각 면에 1부터 6까지의 숫자가 적힌 주사위 N개를 쌓으려고 한다. 이때 주사위의 마주 보는 면에 적힌 숫자의 합은 반드시 7이 되진 않는다. 1번 주사위부터 N번 주사위까지 순서대로 쌓을 때, 두 개의 주사위에서 아래에 있는 주사위의 윗면과 위에 있는 주사위의 아랫면의 숫자는 같아야 한다. N개의 주사위를 세웠을 때 사각 기둥이 세워지게 되고, 사각 기둥의 4개의 옆면 중 어느 한 면의 숫자의 합이 최대가 되도록 쌓아 그 값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 10,000

 

1번 주사위의 윗면을 결정하면 2번부터 N번 주사위의 위 아랫면이 모두 결정된다. 따라서 반복문을 통해 1번 주사위의 윗면을 결정하고 각 주사위의 옆면을 모두 저장한 값의 최댓값을 구하면 된다.

 

A면은 F면과, B면은 D면과, C면은 E면과 마주본다는 것을 고려하고, 아래에 있는 주사위의 윗면 숫자가 주어지면 위에 있는 주사위의 아랫면 인덱스를 구하면서 진행해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, N개의 주사위 정보 입력받기
2. 1번 주사위의 윗면 인덱스를 반복문으로 정하기
   1. 옆면의 합과 위아래 인덱스를 변수로 선언
   2. 1번부터 N번 주사위까지 올리면서 옆면의 합에 최댓값을 더하기
   3. 올리고 나서 위에 올릴 주사위의 위아래 인덱스를 갱신
3. 옆면의 합의 최댓값 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~3회차

• 1번~N번 주사위의 옆면 최댓값을 구할 때 반복문을 N까지가 아닌 6까지로 설정했고, j가 5일 때 break를 걸어둬서 제대로 동작하지 않았음

 

---

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,mx,dice[10001][7];

int sum_mx(int idx, int up, int down) {
    int tmp=0;

    for (int i=0; i<6; i++) {
        if (i==up || i==down) continue;
        tmp = max(tmp,dice[idx][i]);
    }

    return tmp;
}

int counter(int idx) {
    if (idx==0 || idx==5) return 5-idx;
    else if (idx==2 || idx==4) return 6-idx;
    else return 4-idx;
}

int uptodown(int idx, int up_num) {
    for (int i=0; i<6; i++) {
        if (dice[idx][i]==up_num) return i;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> dice[i][0] >> dice[i][1] >> dice[i][2] >> dice[i][3] >> dice[i][4] >> dice[i][5];
    }

    for (int i=0; i<6; i++) { // 1번 주사위 윗면 결정 (a&f, b&d, c&e)
        int sum=0,up_idx=i,down_idx=counter(up_idx);

        for (int j=0; j<n; j++) { // 1번 ~ n번 주사위까지 올리면서 최댓값 더하기
            sum += sum_mx(j,up_idx,down_idx);

            // 주사위 위아래 인덱스 갱신
            down_idx = uptodown(j+1,dice[j][up_idx]);
            up_idx = counter(down_idx);
        }

        mx = max(mx,sum);
    }

    cout  << mx;
}