[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1041번, 주사위

문제 링크

1041번: 주사위

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N×N×N크기의 정육면체를 주사위를 통해서 만듭니다.

2. 탁자에 놓았을 때 보이는 5면의 숫자의 합의 최소값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 정육면체를 만들 때 최소값이 되도록 주사위의 회전을 통해 구성합니다.

 

3. 눈에 보이는 모든 수의 합을 결과로 출력합니다.

 

 

정육면체 만들기

 

 

정육면체를 만들 때 주사위의 면이 보이는 양이 다릅니다.

 

아래와 같은 정육면체일 때가 탁자위에 있을 때

 

※그림판으로 그린 것으로 양해부탁드립니다.

 

 

주사위의 보이는 면이 3개일 때

 

면이 3일 때 : 4개

각 보이는 면이 최소값이 되려면

(C, D)중 작은 값, (E, B) 중 작은 값, (A, F) 중 작은 값이 면으로 보여야 합니다.

 

주사위의 보이는 면이 2개일 때

 

면이 2일 때 : 4 × (N-1) + 4 × (N-2) = 8N - 12개

각 보이는 면이 최소값이 되려면

인접한 면끼리의 합이 최소값이 되는 되어야 합니다.

만약 (A, D)의 합이 최소값이면 정육면체에서 보이는 2면은 A, D입니다.

주사위의 보이는 면이 1개일 때

 

면이 1일 때 : N × N × 5 - (면 2 개수 × 2 + 면 3 개수 × 3)

각 보이는 면이 최소값이 되려면

주사위가 나타내는 값 중에 최소값이 보이는 면이 됩니다.

만약 A의 값이 제일 작다면 정육면체에서는 A의 값이 보여집니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 3

 

2. 정육면체를 만들 때 최소값이 되도록 주사위의 회전을 통해 구성합니다.

 

면 3개일 때 : 4개

 

면에 배치되는 주사위 수

 

(A, F) 중 작은 값 : 1(A)

(E, F) 중 작은 값 : 2(B)

(C, D) 중 작은 값 : 3(C)

면 3개 주사위 수의 합 : 1 + 2 + 3 = 6

 

면 2개일 때 : 8 × N - 12 = 8 × 3 - 12 = 12개

 

면에 배치되는 주사위 수

 

(A, B)의 합이 가장 작으므로 2면에는 A, B가 보여집니다.

면 2개의 주사위 수의 합 : 1 + 2  = 3

면 1개일 때 :

N × N × 5 - (면 2 개수 × 2 + 면 3 개수 × 3)

= 3 × 3 × 5 - (12 × 2 + 4 × 3)

= 45 - 36 = 9개

 

면에 배치되는 주사위 수

주사위의 수가 가장 작은 A가 면이 보여집니다.

면 1개의 주사위 수 : 1 

 

3. 눈에 보이는 모든 수의 합을 결과로 출력합니다.

 

면 3개일 때 : 4 × 6 = 24

 

면 2개일 때 : 12 × 3 = 36

 

면 1개일 때 : 9 × 1 = 9

 

보이는 수의 합 : 24 + 36 + 9 = 69

 

69을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 주사위의 정보를 띄어쓰기 기준 나누었습니다.
• N이 1일 때는 주사위가 정육면체가 되고, 1이상일 때에는 정육면체를 구성합니다.
• 정육면체의 면의 개수, 보여지는 주사위 수의 합을 구합니다.
• 면의 개수와 보여지는 주사위 수의 합을 이용하여 보여지는 모든 수의 합을 구해서 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[6];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int oneNum = Integer.MAX_VALUE;
        //주사위 정보 저장
        for(int i=0;i<6;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            oneNum = Math.min(arr[i], oneNum);	//주사위 수 최대값 구하기
        }
        //N이 1일 때 정육면체를 만드는 것이 아닌 주사위 자체가 정육면체
        if(N==1){
            Arrays.sort(arr);	//오름차순 정렬
            int answer = 0;
            //가장 큰 값을 밑에 있을 때 최소값
            for(int i=0;i<5;i++)
                answer += arr[i];
            bw.write(answer + "");
        }else{
            //N > 1일 때
            long three = 4;	//면 3개 개수
            long two = 4L *(N-1) + (N-2) * 4L;	//면 2개 개수
            long one = (long)N*N*5 - (three*3 + two*2);	//면 1개 개수
            //면 3개일 때 보여지는 수의 합 구하기
            int threeNum = Math.min(arr[0], arr[5]) + 
            		Math.min(arr[1],arr[4]) +  Math.min(arr[2], arr[3]);
            int twoNum = Integer.MAX_VALUE;
            //면 2개일 때 보여지는 수의 합 구하기
            for(int i=0;i<6;i++){
                for(int j=i+1;j<6;j++){
                    //주사위의 마주보는 면은 6이 됩니다.
                    //배열은 0부터 시작되기 때문에 5가 되면 마주보는 면이 됩니다.
                    //마주보는 면은 인접하지 않기 때문에 i+j != 5라는 조건을 사용하였습니다.
                    if(i+j != 5)	
                        twoNum = Math.min(twoNum, arr[i] + arr[j]);
                }
            }
            //보여지는 면 수의 합 계산
            long answer =one * oneNum + two * twoNum + three*threeNum;
            bw.write(answer + "");	//수의 합 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}