[자바] 1041 주사위

자바 / 골5 / 그리디 알고리즘

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

그리디 알고리즘으로 분류되지만 나는 브루트 포스를 이용해서 풀었다.

 

N = 2, 3, 4일 때의 전개도를 생각해 보고 점화식을 만들어 풀었다. 

내가 만든 공식은, a, b, c가 각각 정육면체의 한 면이 포함될 때, 두 면이 포함될 때, 세 면이 포함될 때의 합 값이라면

ans = c * 4 + b * ((2 * N - 3) * 4) + a * ((N - 1) * (N - 2) * 4 + (N - 2) * (N - 2));

 

그리고 a, b, c를 구하는 과정을 각각 브루트 포스로 구했다

a의 값, 즉 주어진 값 중 가장 작은 값을 구하는 코드

        for(int i = 0; i < 6; i++) {
            if (min > dice[i]) {
                idx = i;
                min = dice[i];
            }
            if (max < dice[i]) {
                max = dice[i];
            }
        }
        a = min;

 

a 다음으로 작은 값들 중 a의 값을 갖는 인덱스와 맞은 편에 있지 않되 (a와 한 면에 붙어 있되), 두 번째로 작은 값을 구하여 a에 더해 b를 구한다.

        min = 50;
        for(int i = 0; i < 6; i++) {
            if (idx + i == 5 || i == idx) {
                continue;
            }
            if (min > dice[i]) {
                min = dice[i];
            }
        }
        b = a + min;

 

c의 값은, a나 b에서 구한 값과 맞은편에 있는 값을 제외하고 최솟값을 구해야 하므로 삼중 반복문을 돌려 붙어있는 세 면의 총 합의 최소값을 구했다.

        min = 150;
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                for(int k = 0; k < 6; k++) {
                    if (i + j == 5 || i + k == 5 || k + j == 5 || i == j || i == k || k == j) {
                        continue;
                    }
                    if (min > dice[i] + dice[j] + dice[k]) {
                        min = dice[i] + dice[j] + dice[k];
                    }
                }
            }
        }
        c = min;

 

89%에서 한 번 틀려서, N=1일때의 종료 조건을 잡아 주었다. 입력을 다 받자마자 N = 1인지를 검사하여 맞다면, 각 면의 최대값을 구해 모든 값에서 그 최대값을 뺀 값이 N=1일 때의 해이므로, 이 작업을 a를 계산하기도 전에 먼저 해 주었다.

        if (N == 1) {
            for(int i = 0; i < 6; i++) {
                sum += dice[i];
            }
            sum -= max;
            System.out.println(sum);
            return ;
        }

 

 

마지막으로, 자바에서 정수 자료형 중 long을 넘어가는 크기는 BigInteger라는 자료형으로 처리해줘야 하는데, 이 BigInteger가 숫자 그 자체로 값을 저장하는 게 아닌, 문자열로 숫자를 저장하여 무한대까지도 수를 저장할 수 있도록 하는 자료형이라서 이 자료형을 이용하여 사칙연산을 하는 과정이 꽤 복잡하게 느껴졌다.

        //ans = (c) * 4 + (b) * ((2 * N - 3) * 4) + a * ((N - 1) * (N - 2) * 4 + (N - 2) * (N - 2));

        BigInteger bigN = BigInteger.valueOf(N);
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger bigC = BigInteger.valueOf(c);

        BigInteger term1 = bigC.multiply(BigInteger.valueOf(4));
        BigInteger term2 = bigB.multiply(bigN.multiply(BigInteger.valueOf(2)).subtract(BigInteger.valueOf(3)).multiply(BigInteger.valueOf(4)));
        BigInteger term3 = bigA.multiply(bigN.subtract(BigInteger.valueOf(1)).multiply(bigN.subtract(BigInteger.valueOf(2))).multiply(BigInteger.valueOf(4))
            .add(bigN.subtract(BigInteger.valueOf(2)).multiply(bigN.subtract(BigInteger.valueOf(2)))));

        BigInteger ans = term1.add(term2).add(term3);

 

다음은 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, max = 0, sum = 0, min = 50, idx = -1, a, b, c;
        int [] dice = new int[6];

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

        if (N == 1) {
            for(int i = 0; i < 6; i++) {
                sum += dice[i];
            }
            sum -= max;
            System.out.println(sum);
            return ;
        }
        
        for(int i = 0; i < 6; i++) {
            if (min > dice[i]) {
                idx = i;
                min = dice[i];
            }
            if (max < dice[i]) {
                max = dice[i];
            }
        }
        a = min;

        min = 50;
        for(int i = 0; i < 6; i++) {
            if (idx + i == 5 || i == idx) {
                continue;
            }
            if (min > dice[i]) {
                min = dice[i];
            }
        }
        b = a + min;

        min = 150;
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                for(int k = 0; k < 6; k++) {
                    if (i + j == 5 || i + k == 5 || k + j == 5 || i == j || i == k || k == j) {
                        continue;
                    }
                    if (min > dice[i] + dice[j] + dice[k]) {
                        min = dice[i] + dice[j] + dice[k];
                    }
                }
            }
        }
        c = min;

        //ans = (c) * 4 + (b) * ((2 * N - 3) * 4) + a * ((N - 1) * (N - 2) * 4 + (N - 2) * (N - 2));

        BigInteger bigN = BigInteger.valueOf(N);
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger bigC = BigInteger.valueOf(c);

        BigInteger term1 = bigC.multiply(BigInteger.valueOf(4));
        BigInteger term2 = bigB.multiply(bigN.multiply(BigInteger.valueOf(2)).subtract(BigInteger.valueOf(3)).multiply(BigInteger.valueOf(4)));
        BigInteger term3 = bigA.multiply(bigN.subtract(BigInteger.valueOf(1)).multiply(bigN.subtract(BigInteger.valueOf(2))).multiply(BigInteger.valueOf(4))
            .add(bigN.subtract(BigInteger.valueOf(2)).multiply(bigN.subtract(BigInteger.valueOf(2)))));

        BigInteger ans = term1.add(term2).add(term3);
        System.out.println(ans);
    }
}