[백준] 1041번_주사위 C++
in Study on Coding Test
그리디 알고리즘과 주사위의 수학적 규칙을 활용하는 문제
정답제출코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long N;
vector<long long> cube;
long long sum = 0;
// 3개의 면의 합이 가장 작은 경우를 반환하는 함수
long long cube_min_sum_3()
{
vector<long long> Candidate;
// 서로 이웃한 3개의 면이 노출되는 경우의 수 8가지
Candidate.push_back(cube[0] + cube[1] + cube[2]);
Candidate.push_back(cube[0] + cube[3] + cube[4]);
Candidate.push_back(cube[0] + cube[1] + cube[3]);
Candidate.push_back(cube[0] + cube[2] + cube[4]);
Candidate.push_back(cube[1] + cube[2] + cube[5]);
Candidate.push_back(cube[1] + cube[3] + cube[5]);
Candidate.push_back(cube[2] + cube[4] + cube[5]);
Candidate.push_back(cube[3] + cube[4] + cube[5]);
sort(Candidate.begin(), Candidate.end());
// 정렬 후 가장 작은 값 반환
return Candidate[0];
}
// 2개의 면의 합이 가장 작은 경우를 반환하는 함수
long long cube_min_sum_2()
{
long long set_sum = 10000000;
for (int i = 0; i < 6; ++i)
{
for (int j = 0; j < 6; ++j)
{
if (j == i || j + i == 5)
continue;
if (cube[i] + cube[j] < set_sum)
{
set_sum = cube[i] + cube[j];
}
}
}
return set_sum;
}
long long m_square(long long n)
{
return n * n;
}
// 주사위의 가잔 큰 값을 반환하는 함수
long long m_max()
{
long long m_max = 0;
for (int i = 0; i < 6; ++i)
{
if (cube[i] > m_max)
m_max = cube[i];
}
return m_max;
}
// 주사위의 가장 작은 값을 반환하는 함수
long long cube_min()
{
long long m_min = 51;
for (int i = 0; i < 6; ++i)
{
if (cube[i] < m_min)
m_min = cube[i];
}
return m_min;
}
int main()
{
// 수 입력
cin >> N;
for (int i = 0; i < 6; ++i)
{
long long a;
cin >> a;
cube.push_back(a);
}
if (N == 1)
{
// N = 1인 경우 예외처리
for (int i = 0; i < 6; ++i)
sum += cube[i];
sum -= m_max();
}
else
{
// N >= 2인 경우
// 1개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4*(N-2) + 5*(N-2)^2개 이다.
sum += (cube_min() * (4*(N-2) + 5*m_square(N-2)));
// 2개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4*(N-2) + 4*(N-1)개 이다.
long long sum_set2 = cube_min_sum_2();
sum += (sum_set2 * (4*(N-2) + 4*(N-1)));
// 3개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4개이다.
sum += (4 * cube_min_sum_3());
}
cout << sum;
return 0;
}
주사위를 쌓는데, 어떻게 쌓아야 되도록 가장 작은 값이 출력 되도록 할 수 있을까?
이 과정에서 많이 애를 먹었던 것 같다.
처음에는 단순히 가장 큰 값이 있는 면을 바닥면으로 보내서 안보이게 하면 될 줄 알았다.
#include <iostream>
#include <vector>
using namespace std;
long long N;
long long N_square;
vector<int> cube;
long long sum = 0;
long long cube_max()
{
int m_max = cube[0];
for (int i = 1; i < 6; ++i)
{
if (cube[i] > m_max)
m_max = cube[i];
}
return m_max;
}
int main()
{
// 수 입력
cin >> N;
N_square = N * N;
for (int i = 0; i < 6; ++i)
{
int a;
cin >> a;
cube.push_back(a);
sum += a * N_square;
}
sum -= cube_max() * N_square;
cout << sum;
return 0;
}
하지만 그게 바로 된다면 골드 5 문제가 아니겠지.
역시나 예시 테스트 케이스 1 부터 다른 값이 나왔다.
// 테스트 케이스 1번
2
1 2 3 4 5 6
// 희망 값 : 24
// 출력 값 : 60
아니 근데 테스트 케이스 1번 같은 경우에서 24가 나오는게 정말 가능한거야?
생각을 했는데 생각해보니 가능하긴 하더라.
주사위의 개수
주사위를 쌓아본 모습을 시뮬레이션 해보자.
N이 2일 때
- 3개의 면이 노출되는 주사위의 수는 4개
- 2개의 면이 노출되는 주사위의 수는 4개
- 1개의 면이 노출되는 주사위의 수는 0개
이다.
다음으로 N이 3일 때
- 3개의 면이 노출되는 주사위의 수는 4개
- 2개의 면이 노출되는 주사위의 수는 12개
- 1개의 면이 노출되는 주사위의 수는 9개
- 노출되지 않는 주사위의 수는 2개
다음으로 N이 4일 때
- 3개의 면이 노출되는 주사위의 수는 4개
- 2개의 면이 노출되는 주사위의 수는 20개
- 1개의 면이 노출되는 주사위의 수는 28개
- 노출되지 않는 주사위의 수는 12개
자, 그럼 N이 n일 땐?
- 3개의 면이 노출되는 주사위의 수는 4개
- 2개의 면이 노출되는 주사위의 수는 4(n-2) + 4(n-1)개
- 1개의 면이 노출되는 주사위의 수는 4(n-2) + 5(n-2)^2개
- 노출되지 않는 주사위의 수는 (n-1) * (n-2)^2개
이다.
주사위의 노출 방법
자 그럼 이렇게 노출 될때 되도록 가장 작은 면이 노출되도록 알고리즘을 짜야 한다.
마음 같아선 주사위에 있는 수를 sort 시켜버리고 싶지만,
주사위의 위치라는 규칙도 있기 때문에 함부로 sort시키면 곤란하다.
우선 1개의 면은 그냥 1개만 추출하면 된다.
문제는 2개와 3개일 때 발생한다.
2개의 면이 노출 될 때에는 A를 기준으로 A와 이웃한 면은 B, C, D, E이고, A와 F를 같이 노출시키는 일은 없어야한다.
마찬가지로, B와 이웃한 면은 A, C, D, F이고, B와 E는 같이 노출이 되어선 안된다.
인덱스로 생각해보자. A의 인덱스는 0, B의 인덱스는 1, … F의 인덱스는 5.
재밌는 규칙이 있다. 서로 인접하지 않는 면 끼리의 인덱스의 합은 5이다.
서로 마주보는 쌍 (A(0), F(5)), (B(1), E(4)), (C(2), D(3)) 모두 각각 5이다.
이렇게 조건문을 잘걸어서 continue를 돌리며 알고리즘을 설계하면 되겠지?
// 2개의 면의 합이 가장 작은 경우를 반환하는 함수
long long cube_min_sum_2()
{
long long set_sum = 10000000;
for (int i = 0; i < 6; ++i)
{
for (int j = 0; j < 6; ++j)
{
if (j == i || j + i == 5)
continue;
if (cube[i] + cube[j] < set_sum)
{
set_sum = cube[i] + cube[j];
}
}
}
return set_sum;
}
다음으로 3개일 때 면이 노출되는 경우의 수를 따져보자.
노출이 가능한 경우의 쌍은 아래와 같다.
- (A, B, C) - (0, 1, 2)
- (A, D, E) - (0, 3, 4)
- (A, B, D) - (0, 1, 3)
- (A, C, E) - (0, 2, 4)
- (B, C, F) - (1, 2, 5)
- (B, D, F) - (1, 3, 5)
- (C, E, F) - (2, 4, 5)
- (D, E, F) - (3, 4, 5)
총 8개로, 무식하긴 하지만 그냥 일일이 다 따지는 게 편할 듯 하다.
// 3개의 면의 합이 가장 작은 경우를 반환하는 함수
long long cube_min_index_3()
{
vector<long long> Candidate;
Candidate.push_back(cube[0] + cube[1] + cube[2]);
Candidate.push_back(cube[0] + cube[3] + cube[4]);
Candidate.push_back(cube[0] + cube[2] + cube[4]);
Candidate.push_back(cube[0] + cube[1] + cube[3]);
Candidate.push_back(cube[1] + cube[2] + cube[5]);
Candidate.push_back(cube[1] + cube[3] + cube[5]);
Candidate.push_back(cube[2] + cube[4] + cube[5]);
Candidate.push_back(cube[3] + cube[4] + cube[5]);
sort(Candidate.begin(), Candidate.end());
// 정렬 후 가장 작은 값 반환
return Candidate[0];
}
vector에 후보군을 모두 넣고, 정렬 후 가장 작은 수를 반환하도록 구현하였다.
// 3개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4개이다.
sum += 4 * cube_min_index_3();
그래서 마지막으로 3개의 면이 노출된 경우를 더해준다.
오답제출 기록
쭉쭉 올라가다가 89퍼센트에서 틀렸습니다. 가 떠버려 맞왜틀의 지옥에 빠졌다.
분명 예외케이스가 있다는 것인데.. 뭘까 생각했다.
악!! N = 1 인 경우 를 생각하지 못했다.
반례
1
1 2 3 4 5 6
// 원하는 값 : 15
// 출력된 값 : 13
원인은 아래 부분에 있었다.
// 1개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4*(N-2) + 5*(N-2)^2개 이다.
sum += (cube_min() * (4*(N-2) + 5*m_square(N-2)));
// 2개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4*(N-2) + 4*(N-1)개 이다.
long long sum_set2 = cube_min_sum_2();
sum += (sum_set2 * (4*(N-2) + 4*(N-1)));
// 3개의 면만 노출되는 경우의 가장 작은 값을 노출시킨다.
// 4개이다.
sum += (4 * cube_min_sum_3());
cout << sum;
저 공식들은 N이 2개 이상인 경우에는 유효하지만, N이 1인 경우에는 N-2는 음수가 나오기 때문에
합이 이상해져버린다. 그래서 N=1인 경우를 예외처리 해주어야 한다.
그래서 아래 코드를 추가해 정답제출코드와 같이 바꾸었다.
if (N == 1)
{
// N = 1인 경우 예외처리
for (int i = 0; i < 6; ++i)
sum += cube[i];
sum -= m_max();
}
