[BOJ] 3060 욕심쟁이 돼지 - JAVA

1. 문제

https://www.acmicpc.net/problem/3060

3060번: 욕심쟁이 돼지

돼지는 원형 식탁에 앉아서 식사를 한다. 현수의 돼지들은 기억력이 뛰어나기 때문에 전 날 자신의 양쪽과 맞은편에 앉았던 돼지가 먹었던 양을 기억하고 있다. 또, 욕심도 많기 때문에, 그 만큼의 양을 추가하여 식사를 하기를 원한다.

매일 현수의 집에 신선한 사료가 N만큼 배달된다.

첫 날 돼지들이 먹었던 양이 주어졌을 때, 현수가 6마리의 돼지들의 요구를 들어줄 수 없게 되는 날이 몇 번째 날인지 구하는 프로그램을 작성하시오.

---

2. 풀이

처음에 queue로 풀려고 하다가 맞은 편 돼지 양도 세야되는 걸 깨닫고 list로 변경했다. 그런데 생각해보니 돼지가 매일 먹게 되는 양은 전날의 총합-(나+2자리돼지)-(나+4자리돼지)였다. 여섯마리의 돼지가 이런 식으로 먹는다고 하면 하루에 드는 사료양은 전날*6-전날*2 = 전날*4가 된다.

그래서 사료양이 N보다 크기 직전까지 sum에 4를 곱하고, 결과에 하루를 더해주었다.

import java.io.*;
import java.util.*;

public class BOJ_3060_욕심쟁이돼지 {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());

        for(int tc=0;tc<T;tc++){
            int N = Integer.parseInt(in.readLine());
            st = new StringTokenizer(in.readLine());

            int day = 1;
            long sum = 0;

            for(int i=0;i<6;i++) sum += Integer.parseInt(st.nextToken());


            while(sum<=N) {
                sum *= 4;
                ++day;
            }


            sb.append(day).append("\n");
        }

        System.out.print(sb);
    }
}

---

3. 결과