백준 1041번 - 주사위

문제 풀이

한 면만 보이는 경우, 두 면만 보이는 경우, 세 면이 보이는 경우를 나누어서 생각을 해야한다.
한 면만 보이는 경우는 5(n2)(n2)+4(n2)5 * (n - 2) * (n - 2) + 4 * (n - 2)

두 면만 보이는 경우는 주사위 상에서 두 면이 마주보지 않아야한다 즉, 이웃해야한다.
세 면만 보이는 경우는 주사위 상에서 세 면중 어느 한 쌍도 마주보고 있으면 안된다.

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+     

2면이 보이는 경우는
a + b
a + e
a + d
a + c
b + f
e + f
등, 두면이 마주하지 않는 경우이고.

3면이 보이는 경우는
a + b + d
a + d + e
a + c + e
a + b + c
b + c + f
b + d + f
c + e + f
d + e + f

로 총 8가지다 이 중에 최소를 구하면된다.

문제 링크

boj/1041

소스코드

PS/1041.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;


long  long dice[6];
int main() {
	long long n;
	cin >> n;
	long long  one = 987654321;
	long long two = 987654321;
	long long three = 987654321;
	int m = 0;
	for (int i = 0; i < 6; i++)
	{
		cin >> dice[i];
		one = min(one, dice[i]);
		m = max(m, (int)dice[i]);
	}
	if (n == 1)
	{
		cout << dice[0] + dice[1] + dice[2] + dice[3] + dice[4] + dice[5] - m;
		return 0;
	}
	for (int i = 0; i < 6; i++)
	{
		for (int j = i + 1; j < 6; j++)
		{
			if (i + j != 5)
			{
				two = min(two, dice[i] + dice[j]);
				for (int k = j + 1; k < 6; k++)
				{
					if (j + k != 5 && k + i != 5)
						three = min(three, dice[i] + dice[j] + dice[k]);
				}
			}
		}
	}


	long long p1 = 5 * (n - 2) * (n - 2) + 4 * (n - 2);
	long long p2 = 8 * (n - 2) + 4;

	cout << (p1 * one) + (p2 * two) + (4 * three);
}

좋은 웹페이지 즐겨찾기