각 면에 용이 살고 있는 정육면체가 있다. 용은 음식이 담긴 그릇을 갖고 있고, 음식의 양은 면에 표시된다. 매 차례마다 다음 일이 발생한다: 용은 자기와 근접한 면에 있는 용의 음식을 1/4만큼 가지고 올 수 있다. 정육면체 위쪽에 살고 있는 용들의 대장 스노그의 최종 음식의 양을 구하고 "X/Y" 형태의 문자열로 반환하라.
Constraints
- initialFood는 딱 6개이다.
- initialFood의 원소는 0이상 1000 이하이다.
- initialFood의 원소 순서는 (전, 후, 상, 하, 좌, 우)이다.
- rounds는 0이상 45이하이다.
Code
#include <string>
#include <vector>
using namespace std;
int adj[6][6] = {
{0,0,1,1,1,1},
{0,0,1,1,1,1},
{1,1,0,0,1,1},
{1,1,0,0,1,1},
{1,1,1,1,0,0},
{1,1,1,1,0,0}};
long gcd(long a, long b) {
return (b == 0) ? a : gcd(b,a%b);
}
class Dragons {
public:
string snaug(vector<int> initialFood, int rounds) {
long denom = 2;
long* num = new long[6];
for (int i = 0; i < 6; ++i) num[i] = initialFood[i] * 2;
for (int i = 0; i < rounds; ++i) {
denom *= 2;
long* num2 = new long[6];
for (int j = 0; j < 6; ++j) {
for (int k = 0; k < 6; ++k)
if (adj[j][k] == 1) num2[j] += num[k];
num2[j] /= 2;
}
num = num2;
}
long snum = num[2] / gcd(num[2],denom);
long sdenom = denom / gcd(num[2],denom);
return (sdenom == 1) ? to_string(snum) : to_string(snum) + '/' + to_string(sdenom);
}
};
Explanation
마주보는 면을 제외하고 현재 면과 인접한 면은 4개이므로, 이를 배열로 구현하면 adj 2차원 배열이 나온다. 매 차례마다, 인접한 면의 음식양에 1/4을 곱한 결과값을 현재 면에 더한다. 구하는 값이 실수였으면 이대로 더해나가면 되지만 값을 분수 형태로 표현해야 하므로 다른 접근 방법이 필요하다.
차례1: (a/4+b/4+c/4+d/4) = 1/4 * (a+b+c+d)
차례2: (a/16+b/16+c/16+d/16) = 1/16 * (a+b+c+d)
차례3: ...
a,b,c,d는 매 차례에서 현재 면과 근접한 면의 음식양이다 (그러므로 매 차례마다 값이 바뀐다). 식을 통해 알 수 있는 사실은 1/4을 공통 인수로 뺄 수 있다는 점과, 음식양으로 주어지는 a+b+c+d가 항상 짝수란 점이다 (아래 예 참조). 분자 a+b+c+d는 짝수이고 분모 또한 짝수 4이다. 분모끼리 더해나가고 분자끼리 더해나가면 답이 나온다. 그러나 계산값이 커져 예시를 통과 못하는 문제가 생긴다. 계산값을 줄이기 위해, 분자와 분모의 최대공약수 2를 구해 분자에는 (각 면의 근접한 면을 더한 값 / 2)이고, 분모에는 4/2 = 2를 계속 곱해나가면 된다.
예:
0, 0, 4, 0, 0, 0
1, 1, 0, 0, 1, 1
1/2, 1/2, 1, 1, 1/2, 1/2
=> 처음에 스너그가 살고 있는 전면에만 음식양이 있지만 다음 차례에 근접한 각 면에 살고 있는 용 4마리가 자기 면으로 음식을 4 * 1/4 만큼 가져가므로 a+b+c+d는 항상 짝수이다.
최근 덧글