λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
🎯PS - Baekjoon, etc/κ΅¬ν˜„

πŸ₯‡[λ°±μ€€, 2116] μ£Όμ‚¬μœ„ μŒ“κΈ° (Java)

by hyeon-z 2023. 4. 3.

 

문제 링크

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

 

2116번: μ£Όμ‚¬μœ„ μŒ“κΈ°

μ²«μ€„μ—λŠ” μ£Όμ‚¬μœ„μ˜ κ°œμˆ˜κ°€ μž…λ ₯λœλ‹€. κ·Έ λ‹€μŒ μ€„λΆ€ν„°λŠ” ν•œ 쀄에 ν•˜λ‚˜μ”© μ£Όμ‚¬μœ„μ˜ μ’…λ₯˜κ°€ 1번 μ£Όμ‚¬μœ„λΆ€ν„° μ£Όμ‚¬μœ„ 번호 μˆœμ„œλŒ€λ‘œ μž…λ ₯λœλ‹€. μ£Όμ‚¬μœ„μ˜ μ’…λ₯˜λŠ” 각 면에 μ ν˜€μ§„ μˆ«μžκ°€ κ·Έλ¦Ό1에 μžˆλŠ”

www.acmicpc.net

 

λ‚œμ΄λ„

 

μ‹œκ°„μ œν•œ

2초

 

문제

μ²œμˆ˜λŠ” μ—¬λŸ¬ μ’…λ₯˜μ˜ μ£Όμ‚¬μœ„λ₯Ό κ°€μ§€κ³  μŒ“κΈ° 놀이λ₯Ό ν•˜κ³  μžˆλ‹€. μ£Όμ‚¬μœ„μ˜ λͺ¨μ–‘은 λͺ¨λ‘ 크기가 같은 μ •μœ‘λ©΄μ²΄μ΄λ©° 각 λ©΄μ—λŠ” 1λΆ€ν„° 6κΉŒμ§€μ˜ μˆ«μžκ°€ ν•˜λ‚˜μ”© μ ν˜€μžˆλ‹€. κ·ΈλŸ¬λ‚˜ 보톡 μ£Όμ‚¬μœ„μ²˜λŸΌ 마주 λ³΄λŠ” 면에 적힌 숫자의 합이 λ°˜λ“œμ‹œ 7이 λ˜λŠ” 것은 μ•„λ‹ˆλ‹€.

 

μ£Όμ‚¬μœ„ μŒ“κΈ° λ†€μ΄λŠ” μ•„λž˜μ—μ„œλΆ€ν„° 1번 μ£Όμ‚¬μœ„, 2번 μ£Όμ‚¬μœ„, 3번 μ£Όμ‚¬μœ„, … 의 μˆœμ„œλ‘œ μŒ“λŠ” 것이닀. μŒ“μ„ λ•Œ λ‹€μŒκ³Ό 같은 κ·œμΉ™μ„ μ§€μΌœμ•Ό ν•œλ‹€: μ„œλ‘œ λΆ™μ–΄ μžˆλŠ” 두 개의 μ£Όμ‚¬μœ„μ—μ„œ μ•„λž˜μ— μžˆλŠ” μ£Όμ‚¬μœ„μ˜ μœ—λ©΄μ— μ ν˜€μžˆλŠ” μˆ«μžλŠ” μœ„μ— μžˆλŠ” μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ— μ ν˜€μžˆλŠ” μˆ«μžμ™€ κ°™μ•„μ•Ό ν•œλ‹€. λ‹€μ‹œ λ§ν•΄μ„œ, 1번 μ£Όμ‚¬μœ„ μœ—λ©΄μ˜ μˆ«μžλŠ” 2번 μ£Όμ‚¬μœ„ μ•„λž«λ©΄μ˜ μˆ«μžμ™€ κ°™κ³ , 2번 μ£Όμ‚¬μœ„ μœ—λ©΄μ˜ μˆ«μžλŠ” 3번 μ£Όμ‚¬μœ„ μ•„λž«λ©΄μ˜ μˆ«μžμ™€ κ°™μ•„μ•Ό ν•œλ‹€. 단, 1번 μ£Όμ‚¬μœ„λŠ” λ§ˆμŒλŒ€λ‘œ 놓을 수 μžˆλ‹€.

 

μ΄λ ‡κ²Œ μŒ“μ•„ λ†“μœΌλ©΄ κΈ΄ 사각기λ‘₯이 λœλ‹€. 이 사각기λ‘₯μ—λŠ” 4개의 κΈ΄ μ˜†λ©΄μ΄ μžˆλ‹€. 이 4개의 μ˜†λ©΄ μ€‘μ—μ„œ μ–΄λŠ ν•œ 면의 숫자의 합이 μ΅œλŒ€κ°€ λ˜λ„λ‘ μ£Όμ‚¬μœ„λ₯Ό μŒ“κ³ μž ν•œλ‹€. μ΄λ ‡κ²Œ ν•˜κΈ° μœ„ν•˜μ—¬ 각 μ£Όμ‚¬μœ„λ₯Ό μœ„μ•„λž˜λ₯Ό κ³ μ •ν•œ 채 μ˜†μœΌλ‘œ 90도, 180도, λ˜λŠ” 270도 돌릴 수 μžˆλ‹€. ν•œ μ˜†λ©΄μ˜ 숫자의 ν•©μ˜ μ΅œλŒ“κ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

 

μž…λ ₯

μ²«μ€„μ—λŠ” μ£Όμ‚¬μœ„μ˜ κ°œμˆ˜κ°€ μž…λ ₯λœλ‹€. κ·Έλ‹€μŒ μ€„λΆ€ν„°λŠ” ν•œ 쀄에 ν•˜λ‚˜μ”© μ£Όμ‚¬μœ„μ˜ μ’…λ₯˜κ°€ 1번 μ£Όμ‚¬μœ„λΆ€ν„° μ£Όμ‚¬μœ„ 번호 μˆœμ„œλŒ€λ‘œ μž…λ ₯λœλ‹€. μ£Όμ‚¬μœ„μ˜ μ’…λ₯˜λŠ” 각 면에 적힌 μˆ«μžκ°€ κ·Έλ¦Ό 1에 μžˆλŠ” μ£Όμ‚¬μœ„μ˜ μ „κ°œλ„μ—μ„œ A, B, C, D, E, F의 μˆœμ„œλ‘œ μž…λ ₯λœλ‹€. μž…λ ₯λ˜λŠ” 숫자 μ‚¬μ΄μ—λŠ” 빈칸이 ν•˜λ‚˜μ”© μžˆλ‹€. μ£Όμ‚¬μœ„μ˜ κ°œμˆ˜λŠ” 10,000개 μ΄ν•˜μ΄λ©° μ’…λ₯˜κ°€ 같은 μ£Όμ‚¬μœ„λ„ μžˆμ„ 수 μžˆλ‹€.

 

좜λ ₯

첫쀄에 ν•œ μ˜†λ©΄μ˜ 숫자의 합이 κ°€μž₯ 큰 값을 좜λ ₯ν•œλ‹€.

 

μž…μΆœλ ₯ μ˜ˆμ‹œ

μž…λ ₯

5
2 3 1 6 5 4
3 1 2 4 6 5
5 6 4 1 3 2
1 3 6 2 4 5
4 1 6 5 2 3

 

좜λ ₯

29

 


문제 풀이 κ³Όμ •

 λ¬Έμ œ μ΄ν•΄ν•˜κΈ°

 

λ¨Όμ € μ£Όμ‚¬μœ„ κ·Έλ¦Ό 1을 μ‚΄νŽ΄λ³΄μž.

A의 λ°˜λŒ€ νŽΈμ—λŠ” F, B의 λ°˜λŒ€νŽΈμ—λŠ” D, C의 λ°˜λŒ€νŽΈμ—λŠ” Eκ°€ μžˆλ‹€λŠ” 것을 μ•Œ 수 μžˆλ‹€.

즉, 짝을 맞좰보면 A-F, B-D, C-E이닀.

 

β“λ§€λ²ˆ μ΅œμ„ μ˜ 선택을 ν•˜λ©΄ κ³Όμ—° μ£Όμ‚¬μœ„ μ˜†λ©΄μ˜ 숫자의 ν•©μ˜ μ΅œλŒ“κ°’μ„ ꡬ할 수 μžˆμ„κΉŒ?

닡은 "μ•„λ‹ˆλ‹€"이닀.

 

κ·Έ μ΄μœ λŠ” 첫 번째 μ£Όμ‚¬μœ„μ—μ„œ μ•„λž«λ©΄μœΌλ‘œ 1, 즉 μ΅œμ†Œμ˜ 수λ₯Ό μ„ νƒν–ˆλ‹€κ³  해도 그와 짝인 μˆ˜κ°€ 6으둜 μ΅œλŒ€μΌ 수 있기 λ•Œλ¬Έμ΄λ‹€.

λ”°λΌμ„œ 첫 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ„ 1λΆ€ν„° 6κΉŒμ§€ κ³ μ •μ‹œμΌœ κ°€λ©° ν•΄λ‹Ή κ²½μš°μ— λ”°λ₯Έ μ˜† 면의 μ΅œλŒ“κ°’μ„ κ΅¬ν•œ λ‹€μŒ 그쀑 κ°€μž₯ 큰 값을 ꡬ해야 ν•œλ‹€.

 

μž…λ ₯κ°’ μ €μž₯ν•˜κΈ°

 

public class BOJ_2116 {
    static int[][] dice;
    static final int diceCount = 6;
    static int[] diceMatch = {5, 3, 4, 1, 2, 0};  // A-F, B-D, C-E

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        dice = new int[N][diceCount];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < diceCount; j++) {
                dice[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

 

μœ„μ—μ„œ μ‚΄νŽ΄λ΄€λ˜ A-F, B-D, C-Eλ₯Ό 인덱슀둜 ν‘œν˜„ν•˜λ©΄ 0-5, 1-3, 2-4κ°€ λ˜μ–΄ dicMatchλ³€μˆ˜μ— μ €μž₯ν•œλ‹€.

κ·Έ ν›„ 이쀑 for문을 λŒλ©΄μ„œ μ£Όμ‚¬μœ„μ˜ 정보λ₯Ό diceλ³€μˆ˜μ— μ €μž₯ν•œλ‹€.

 

 μ²« 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ„ 1λΆ€ν„° 6κΉŒμ§€ κ³ μ •μ‹œν‚€λ©° ν•΄λ‹Ή 경우 μ‚΄νŽ΄λ³΄κΈ°

 

int result = 0;

for (int i = 0; i < diceCount; i++) {
    int bottom = dice[0][i];
    ...

    for (int j = 1; j < N; j++) {
        ...
    }

    result = Math.max(totalMax, result);
}

 

for문을 돌며 첫 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ„ κ³ μ •μ‹œν‚¨λ‹€.

 

β“κ·Έλ‹€μŒμœΌλ‘œλŠ” μ–΄λ–€ 일을 ν•΄μ•Ό ν• κΉŒ?

1. ν•΄λ‹Ή μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ— λ”°λ₯Έ λ‹€μŒ μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ˜ indexλ₯Ό κ΅¬ν•œλ‹€.

2. λ‹€μŒ μ£Όμ‚¬μœ„ μ•„λž«λ©΄μ˜ indexλ₯Ό 톡해 ν•΄λ‹Ή μ£Όμ‚¬μœ„μ˜ μœ—λ©΄μ˜ index와 μ•„λž«λ©΄μ˜ indexλ₯Ό μ œμ™Έν•œ indexλ₯Ό μ‚΄νŽ΄λ³΄λ©° μ΅œλŒ“κ°’μ„ κ΅¬ν•˜μ—¬ μ˜†λ©΄μ˜ μ΅œλŒ“κ°’μ„ κ΅¬ν•œλ‹€.

 

즉, 첫 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ„ κ³ μ •μ‹œν‚€λ©΄ λ‹€μŒ 쑰건에 따라 λ‹€μŒ μ£Όμ‚¬μœ„μ˜ μœ—λ©΄κ³Ό μ•„λž«λ©΄μ€ μ •ν•΄μ§€κ²Œ λœλ‹€.

μ„œλ‘œ λΆ™μ–΄ μžˆλŠ” 두 개의 μ£Όμ‚¬μœ„μ—μ„œ μ•„λž˜μ— μžˆλŠ” μ£Όμ‚¬μœ„μ˜ μœ—λ©΄μ— μ ν˜€μžˆλŠ” μˆ«μžλŠ” μœ„μ— μžˆλŠ” μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ— μ ν˜€μžˆλŠ” μˆ«μžμ™€ κ°™μ•„μ•Ό ν•œλ‹€.

 

λ˜ν•œ λ¬Έμ œμ— λ‹€μŒκ³Ό 같이 μœ„μ•„λž˜λ₯Ό κ³ μ •ν•œ 채 μ˜†μœΌλ‘œ 돌릴 수 μžˆλ‹€λŠ” 쑰건이 μžˆμœΌλ―€λ‘œ λ§€ μ£Όμ‚¬μœ„λ§ˆλ‹€ μœ—λ©΄κ³Ό μ•„λž«λ©΄μ„ μ œμ™Έν•œ κ°’ 쀑 μ΅œλŒ“κ°’μ„ 찾으며 더해주면 λœλ‹€.

μ΄λ ‡κ²Œ ν•˜κΈ° μœ„ν•˜μ—¬ 각 μ£Όμ‚¬μœ„λ₯Ό μœ„μ•„λž˜λ₯Ό κ³ μ •ν•œ 채 μ˜†μœΌλ‘œ 90도, 180도, λ˜λŠ” 270도 돌릴 수 μžˆλ‹€. 

 

index+1번째 μ£Όμ‚¬μœ„ μ•„λž«λ©΄ 숫자둜 λ‹€μŒ μ£Όμ‚¬μœ„ μ•„λž«λ©΄ index μ°ΎκΈ°

 

static int findNextBottomIndex(int index, int bottom) {
    int nBottomIndex = 0;

    for (int i = 0; i < diceCount; i++) {
        if (dice[index][i] == bottom) {
            nBottomIndex = diceMatch[i];
            break;
        }
    }

    return nBottomIndex;
}

 

첫 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ€ κ³ μ •μ‹œν‚€κΈ° λ•Œλ¬Έμ— 두 λ²ˆμ§ΈλΆ€ν„° λ§ˆμ§€λ§‰ μ£Όμ‚¬μœ„κΉŒμ§€ λ°˜λ³΅λ¬Έμ„ 돌며 μ£Όμ‚¬μœ„μ˜ 6면을 μ‚΄νŽ΄λ³΄κ³  bottomκ³Ό 같은 μˆ˜κ°€ λ‚˜μ˜€λ©΄ ν•΄λ‹Ή μ£Όμ‚¬μœ„μ˜ μœ—λ©΄μ˜ indexλ₯Ό μ•Œκ²Œ λœλ‹€. diceMatch배열을 톡해 ν•΄λ‹Ή μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄ indexλ₯Ό 찾은 ν›„ return ν•œλ‹€.

 

μ•„λž«λ©΄ indexλ₯Ό 톡해 μ˜†λ©΄μ˜ μ΅œλŒ“κ°’ μ°ΎκΈ°

 

static int findMax(int index, int bottomIndex) {
    int max = 0;

    for (int i = 0; i < diceCount; i++) {
        if (i == bottomIndex || i == diceMatch[bottomIndex]) {
            continue;
        }
        if (max < dice[index][i]) {
            max = dice[index][i];
        }
    }

    return max;
}

 

ν•΄λ‹Ή μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄κ³Ό μœ—λ©΄μ˜ indexλ₯Ό μ œμ™Έν•œ κ°’ 쀑 λ°˜λ³΅λ¬Έμ„ 돌며 μ΅œλŒ“κ°’μ„ μ°Ύμ•„λ‚΄κ³  이λ₯Ό return ν•œλ‹€.

 

μ΅œμ’… μ½”λ“œ

 

public class BOJ_2116 {
    static int[][] dice;
    static final int diceCount = 6;
    static int[] diceMatch = {5, 3, 4, 1, 2, 0};  // A-F, B-D, C-E

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        dice = new int[N][diceCount];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < diceCount; j++) {
                dice[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0;

        for (int i = 0; i < diceCount; i++) {
            int bottom = dice[0][i];
            int totalMax = findMax(0, i);

            for (int j = 1; j < N; j++) {
                int nBottomIndex = findNextBottomIndex(j, bottom);
                totalMax += findMax(j, nBottomIndex);
                bottom = dice[j][nBottomIndex];
            }

            result = Math.max(totalMax, result);
        }

        System.out.println(result);
    }

    // index+1번째 μ£Όμ‚¬μœ„ μ•„λž«λ©΄ 숫자둜 λ‹€μŒ μ£Όμ‚¬μœ„ μ•„λž«λ©΄ index μ°ΎκΈ°
    static int findNextBottomIndex(int index, int bottom) {
        int nBottomIndex = 0;

        for (int i = 0; i < diceCount; i++) {
            if (dice[index][i] == bottom) {
                nBottomIndex = diceMatch[i];
                break;
            }
        }

        return nBottomIndex;
    }

    static int findMax(int index, int bottomIndex) {
        int max = 0;

        for (int i = 0; i < diceCount; i++) {
            if (i == bottomIndex || i == diceMatch[bottomIndex]) {
                continue;
            }
            if (max < dice[index][i]) {
                max = dice[index][i];
            }
        }

        return max;
    }
}

 μ²« 번째 μ£Όμ‚¬μœ„μ˜ μ•„λž«λ©΄μ„ 1λΆ€ν„° 6κΉŒμ§€ κ³ μ •μ‹œν‚€λ©° μ˜† 면의 μ΅œλŒ“κ°’μ„ κ΅¬ν•œ λ’€ 그쀑 κ°€μž₯ 큰 값을 좜λ ₯ν•œλ‹€.

 

λŒ“κΈ€