[C++] 백준 3060번 풀이 ( 욕심쟁이 돼지 )

- 문제 ( 3060번 ) : 욕심쟁이 돼지

• 링크 : https://www.acmicpc.net/problem/3060

• 하루에 제공받는 사료의 양과 첫날 돼지들이 먹었던 양이 주어졌을 때, 6마리 돼지들의 요구를 들어줄 수 없게 되는 날이 몇번째 날인지 구하는 프로그램 작성.

  • 돼지들은 욕심이 많기 때문에 하루가 지날 때마다 다음과 같이 먹는양이 변한다.
    => [ 전날 자신이 먹은 양 + 본인의 양쪽, 맞은편 돼지가 전날 먹은 양 ] 을 먹음.

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄의 testcase 개수 T 입력
• 각 testcase 는 두줄로 구성되어있으며
  -- 첫째 줄에는 하루에 배달되는 사료의 양 N (1 ≤ N ≤ 500,000,000)
  -- 1, 2, 3, 4, 5, 6번 돼지가 첫 날 먹었던 식사의 양을 빈칸을 사이에 두고 차례로 입력 ( 각 돼지가 먹는 사료의 양은 100 이하 자연수이다. )

[ 출력 ]

• 각 testcase 에 대해 6마리 돼지의 요구를 모두 들어줄 수 없게 되는 날이 몇 번째 날인지 출력.
  즉, [ 하루에 제공받은 사료의 양 ≤ 돼지가 먹은 양 ] 인 날 출력.

---

- 문제 풀이

• 이 문제는 day 를 하루씩 늘려가며 6마리의 돼지가 먹는 양을 계산해 그 날 제공받는 사료의 양과 비교해 문제를 해결하면 된다.

• 각 돼지가 먹는 사료의 양은 다음과 같이 update 된다.

  1. day1 인 경우 : 입력받은 양
  2. 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;
}