BOJ 1041 - 주사위

문제

BOJ 1041 - 주사위

N×N×N 크기의 정육면체를 N개의 주사위로 쌓는다. 주사위의 6면에는 각각 숫자가 적혀 있다. 정육면체의 윗면을 제외한 5면에서 보이는 면의 합의 최솟값을 구한다.

주사위 면 배열: a b c d e f (1-indexed)로 입력, 반대 면의 합은 a+f=const가 아니라 인덱스 i와 5-i가 반대 면 관계
N=1일 때는 특수 처리 필요

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에 주사위 6면의 숫자가 주어진다.

출력

보이는 면의 합의 최솟값을 출력한다.

예제

입력:

2
1 2 3 4 5 6

출력:

풀이

핵심 아이디어: 보이는 면의 종류를 한 면만 보이는 면, 두 면이 보이는 모서리, 세 면이 보이는 꼭짓점으로 나눠 각각 최솟값 면을 그리디하게 선택한다.

보이는 면의 개수 (N≥2 기준):

1면 노출: 5(N-2)^2 + 4(N-2) → 최솟값 하나의 면(전체 6면 중 최솟값)
2면 노출(모서리): 8(N-2) + 4 → 주사위를 회전하여 인접한 두 면의 합이 최소인 조합 (반대 면 제외)
3면 노출(꼭짓점): 4 → 인접한 세 면의 합이 최소인 조합

계산 방법:

전체 최솟값 min을 1면 노출 자리에 사용한다.
반대 면이 아닌 두 면 조합 중 합이 최솟값을 모서리 자리에 사용한다.
꼭짓점 4개는 세 쌍의 반대 면(arr[i]와 arr[5-i]) 중 작은 값의 합을 사용한다.
N=1이면 5면 모두 보이므로 6면 중 최댓값을 제외한 합을 출력한다.

코드

package com.ssafy.an.day199;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
public class Day196BOJ1041주사위 { // 1041 주사위 구
	static long N;
	static int[] arr = new int[6];
	static long[] num = new long[4];
	static long res;
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
		N = Integer.parseInt(br.readLine());
 
		num[1] = 5 * (N - 2) * (N - 2) + 4 * (N - 2);
		num[2] = 8 * (N - 2) + 4;
		num[3] = 4;
 
		String[] sarr = br.readLine().split(" ");
		for (int i = 0; i < 6; i++)
			arr[i] = Integer.parseInt(sarr[i]);
 
		if (N == 1) {
			Arrays.sort(arr);
			int sum = 0;
			for (int i = 0; i < 5; i++) {
				sum += arr[i];
			}
			bw.write(sum + "\n");
		}
 
		else {
			long min = arr[0];
			for (int i = 1; i < 6; i++) {
				min = Math.min(min, arr[i]);
			}
			res += num[1] * min;
 
			min = Long.MAX_VALUE;
			for (int i = 0; i < 6; i++) {
				for (int j = i + 1; j < 6; j++) {
					if (j + i != 5) {
						min = Math.min(min, arr[i] + arr[j]);
					}
				}
			}
			res += num[2] * min;
 
			int sum = 0;
			for (int i = 0; i < 3; i++) {
				sum += Math.min(arr[i], arr[5 - i]);
			}
			res += num[3] * sum;
 
			bw.write(res + "\n");
		}
		bw.flush();
	}
}

복잡도

시간: O(1) — 6면 상수 크기의 반복 연산만 수행
공간: O(1) — 상수 크기의 배열 사용

문제

BOJ 1041 - 주사위

주사위 면 배열: a b c d e f (1-indexed)로 입력, 반대 면의 합은 a+f=const가 아니라 인덱스 i와 5-i가 반대 면 관계
N=1일 때는 특수 처리 필요

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에 주사위 6면의 숫자가 주어진다.

출력

보이는 면의 합의 최솟값을 출력한다.

예제

입력:

2
1 2 3 4 5 6

출력:

풀이

보이는 면의 개수 (N≥2 기준):

1면 노출: 5(N-2)^2 + 4(N-2) → 최솟값 하나의 면(전체 6면 중 최솟값)
2면 노출(모서리): 8(N-2) + 4 → 주사위를 회전하여 인접한 두 면의 합이 최소인 조합 (반대 면 제외)
3면 노출(꼭짓점): 4 → 인접한 세 면의 합이 최소인 조합

계산 방법:

전체 최솟값 min을 1면 노출 자리에 사용한다.
반대 면이 아닌 두 면 조합 중 합이 최솟값을 모서리 자리에 사용한다.
꼭짓점 4개는 세 쌍의 반대 면(arr[i]와 arr[5-i]) 중 작은 값의 합을 사용한다.
N=1이면 5면 모두 보이므로 6면 중 최댓값을 제외한 합을 출력한다.

코드

package com.ssafy.an.day199;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
public class Day196BOJ1041주사위 { // 1041 주사위 구
	static long N;
	static int[] arr = new int[6];
	static long[] num = new long[4];
	static long res;
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
		N = Integer.parseInt(br.readLine());
 
		num[1] = 5 * (N - 2) * (N - 2) + 4 * (N - 2);
		num[2] = 8 * (N - 2) + 4;
		num[3] = 4;
 
		String[] sarr = br.readLine().split(" ");
		for (int i = 0; i < 6; i++)
			arr[i] = Integer.parseInt(sarr[i]);
 
		if (N == 1) {
			Arrays.sort(arr);
			int sum = 0;
			for (int i = 0; i < 5; i++) {
				sum += arr[i];
			}
			bw.write(sum + "\n");
		}
 
		else {
			long min = arr[0];
			for (int i = 1; i < 6; i++) {
				min = Math.min(min, arr[i]);
			}
			res += num[1] * min;
 
			min = Long.MAX_VALUE;
			for (int i = 0; i < 6; i++) {
				for (int j = i + 1; j < 6; j++) {
					if (j + i != 5) {
						min = Math.min(min, arr[i] + arr[j]);
					}
				}
			}
			res += num[2] * min;
 
			int sum = 0;
			for (int i = 0; i < 3; i++) {
				sum += Math.min(arr[i], arr[5 - i]);
			}
			res += num[3] * sum;
 
			bw.write(res + "\n");
		}
		bw.flush();
	}
}

복잡도

시간: O(1) — 6면 상수 크기의 반복 연산만 수행
공간: O(1) — 상수 크기의 배열 사용