백준 1041번: 주사위

[문제 링크]

1041번: 주사위

---

쉬운 문제였음에도 불구하고 고생했던 문제였다.

 

먼저 정육면체를 만들었을 때 1면이 보이는 주사위, 2면이 보이는 주사위, 3면이 보이는 주사위로 이루어져 있음을 알 수 있다.

 

또한 이 주사위들의 갯수는 N에 따라 달라지는데 공식은 다음과 같다.

 

1면이 보이는 주사위의 개수 = (N - 2)^2 * 5 + (N - 2) * 4

2면이 보이는 주사위의 개수 = (N - 2) * 8 + 4

3면이 보이는 주사위의 개수 = 4

 

따라서 여섯면 중 최솟값, 인접한 2면을 더했을 때 최솟값, 인접한 3면을 더했을 때 최솟값을 각각 구해준 다음 계산해주면 된다.

 

예외로 N이 1일 때는 주사위 한개만 놓으므로 (6면 전체 값 - 최댓값)이 정답이 된다.

 

N이 최대 100만이므로 (N-2)^2 연산에서 int 범위를 초과하게 되기 때문에 long long 자료형을 사용했다.

 

제대로 구현했음에도 불구하고 계속해서 오답을 맞아서 고생했는데, 원인은 변수 N에 있었다.

 

Greedy() 함수에서 매개변수로 받는 N이 int 형이기 때문에 (N - 2) ^ 2 연산에서 가장 좌측에 있는 N의 자료형을 기준으로 묵시적 형변환되어 오버플로가 발생했던 것이었다.

 

좌변에 long long 자료형으로 선언한 ret 변수가 있었기 때문에 묵시적 형변환이 일어나지 않을거라 생각하여 디버깅하는데 오래 걸렸던거 같다.

---

#include <iostream>
using namespace std;

const int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5;
const int INF = 987654321;

int dice[6];
int twoX[12] = { A,A,A,A,B,B,B,C,C,D,D,E };
int twoY[12] = { B,C,D,E,C,D,F,E,F,E,F,F };
int threeX[8] = { A,A,A,A,B,B,C,D };
int threeY[8] = { B,B,C,D,C,D,E,E };
int threeZ[8] = { C,D,E,E,F,F,F,F };

int min(int a, int b) { return a < b ? a : b; }

long long Greedy(int N, int minNum)
{
	int twoSum = INF, threeSum = INF;

	for (int i = 0; i < 12; i++)
		twoSum = min(twoSum, dice[twoX[i]] + dice[twoY[i]]);

	for (int i = 0; i < 8; i++)
		threeSum = min(threeSum, dice[threeX[i]] + dice[threeY[i]] + dice[threeZ[i]]);

	long long one = (long long) (N - 2) * (N - 2) * 5 + (N - 2) * 4;
	long long two = (N - 2) * 8 + 4;
	long long ret = 0;

	ret += one * minNum;
	ret += two * twoSum;
	ret += 4 * threeSum;

	return ret;
}

int main(void)
{
	int N;
	cin >> N;

	int maxNum = 0, minNum = INF, sum = 0;

	for (int i = 0; i < 6; i++)
	{
		cin >> dice[i];

		if (N == 1)
		{
			sum += dice[i];
			maxNum = maxNum > dice[i] ? maxNum : dice[i];
		}
		else
			minNum = minNum < dice[i] ? minNum : dice[i];
	}

	if (N == 1)
		cout << sum - maxNum << endl;
	else
		cout << Greedy(N, minNum) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 129 day