1일차 (월) : 2116번, 주사위 쌓기 ****(G5)

문제 : 단순 구현 문제이다. 주사위의 방향을 헷갈리지 않도록 주의하면 쉽게 해결할 수 있다.

풀이과정

1. 첫번째 주사위 6면을 각각 밑면으로 시작하는 6가지 경우를 모두 탐색한다.
2. 재귀를 통해 각각의 경우에서 N번째 주사위까지 탐색한다.
3. 탐색을 위해 3가지 함수를 만든다. (다음 주사위, 주사위 반대편, 옆면 최대값)을 구하는 함수이다.
4. 시간복잡도 O(66N)으로 풀이할 수 있다
5. 정답

풀이 코드

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int find_nxt(int n, int i, int s);
int find_max(int n, int i);
int find_top(int i);

vector<vector<int>> dice;
int N;

int find_nxt(int n, int i, int s) {
    if (n + 1 == N)
        return s;

    int top = find_top(i);
    for (int nxt = 0; nxt < 6; nxt++) {
        if (dice[n][top] == dice[n + 1][nxt]) {
            return find_nxt(n + 1, nxt, s + find_max(n + 1, nxt));
        }
    }
}

int find_top(int i) {
    int top;
    if (i == 0)
        top = 5;
    else if (i == 1)
        top = 3;
    else if (i == 2)
        top = 4;
    else if (i == 3)
        top = 1;
    else if (i == 4)
        top = 2;
    else
        top = 0;

    return top;
}

int find_max(int n, int i) {
    int top = find_top(i);

    int tmp = 0;
    for (int m = 0; m < 6; m++) {
        if (m == i || m == top) continue;
        tmp = max(tmp, dice[n][m]);
    }
    return tmp;
}

int main() {
    fastio;
    
    cin >> N;
    dice.resize(N);

    for (int i = 0; i < N; i++) {
        dice[i].resize(6);
        int a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        dice[i] = { a, b, c, d, e, f };
    }

    int chk = 0;
    for (int idx_under = 0; idx_under < 6; idx_under++) 
        chk = max(chk, find_nxt(0, idx_under, find_max(0, idx_under)));

    cout << chk << "\\n";
    return 0;
}

최종수정 : 2025-02-19

2일차 (화) : 2230번, 수 고르기 ****(G5)