- 돼지들은 욕심이 많기 때문에 하루가 지날 때마다 다음과 같이 먹는양이 변한다.
=> [ 전날 자신이 먹은 양 + 본인의 양쪽, 맞은편 돼지가 전날 먹은 양 ] 을 먹음.
[ 입력 ]
- 첫째 줄의 testcase 개수 T 입력
- 각 testcase 는 두줄로 구성되어있으며
-- 첫째 줄에는 하루에 배달되는 사료의 양 N (1 ≤ N ≤ 500,000,000)
-- 1, 2, 3, 4, 5, 6번 돼지가 첫 날 먹었던 식사의 양을 빈칸을 사이에 두고 차례로 입력 ( 각 돼지가 먹는 사료의 양은 100 이하 자연수이다. )
[ 출력 ]
- 각 testcase 에 대해 6마리 돼지의 요구를 모두 들어줄 수 없게 되는 날이 몇 번째 날인지 출력.
즉, [ 하루에 제공받은 사료의 양 ≤ 돼지가 먹은 양 ] 인 날 출력.
이 문제는 day 를 하루씩 늘려가며 6마리의 돼지가 먹는 양을 계산해 그 날 제공받는 사료의 양과 비교해 문제를 해결하면 된다.
각 돼지가 먹는 사료의 양은 다음과 같이 update 된다.
- day1 인 경우 : 입력받은 양
- day2 이상인 경우 : 4가지 경우의 사료 양 합산
전날먹은 양 + 왼쪽돼지가 전날먹은 양 +
오른쪽돼지가 전날먹은 양 + 맞은편 돼지가 전날 먹은 양
이렇게 하루에 소비하는 사료의 양을 구하기만 한다면 아래와 같은 비교를 통해 결과를 출력하면 된다.
- [ 하루에 제공받은 사료의 양 ≤ 돼지가 먹은 양 ] 인 경우
=> 이 날을 출력 ( day6 이었다면 "6" 출력 )
#include <iostream>
#include <algorithm>
int pig[6] = {0, };
int prev_pig[6] = {0, };
int calc_use_feed(int day) {
int result = 0;
if(day != 1) {
for(int i = 0; i < 6; i++) {
int left = (i + 6 - 1) % 6;
int right = (i + 6 + 1) % 6;
int opposite = (i + 3) % 6;
pig[i] = prev_pig[i] + prev_pig[left] + prev_pig[right] + prev_pig[opposite];
}
std::copy(pig, pig+6, prev_pig);
}
for(int i = 0; i < 6; i++) {
result += pig[i];
}
return result;
}
int main() {
int T = 0; // the number of testcase
std::cin >> T;
for(int i = 0; i < T; i++) {
int day = 1;
int N = 0; // amount of feed
std::cin >> N;
for(int j = 0; j < 6; j++) {
std::cin >> pig[j];
prev_pig[j] = pig[j];
}
while(true) {
int use_feed = calc_use_feed(day);
// terminate condition : use_feed > N
if(use_feed > N) {
std::cout << day << std::endl;
break;
}
// not terminated
day++;
}
}
return 0;
}