[백준] 3060번 욕심쟁이 돼지 [Python] - 등비수열

매일 N만큼의 사료로 돼지를 먹일 수 있다.

N과 첫 날 돼지들이 먹은 양이 주어진다.

 

돼지들은 매일 전날 자신이 먹었던 양에 양 옆 돼지들과 맞은 편의 돼지가 먹었던 양까지 더해서 먹고 싶어한다.

돼지들의 요구를 들어줄 수 없게 되는 날을 구하는 문제

문제

유명한 농부 박현수는 돼지 6마리를 키우고 있다. 그는 하루에 한 번씩 돼지에게 맛있는 밥을 준다.

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

예를 들어, 현수가 1번부터 6번까지 돼지에게 각각 3, 2, 7, 1, 5, 4만큼 밥을 주었다면, 2번 돼지는 첫 날 받은 양 2에다 양쪽과 맞은편 돼지가 받은 양 15$($3+7+5$)$만큼을 더해 17만큼 받기를 원한다.

마음씩 좋은 농부 박현수는 이런 돼지의 요구를 모두 들어주려고 한다. 매일 현수의 집에 신선한 사료가 N만큼 배달된다. 사료의 유통기한은 하루이기 때문에, 남은 사료는 모두 폐기한다.

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

입력

입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 줄로 구성되어 있고, 첫째 줄에는 하루에 배달되는 사료의 양 N (1<=N<=500,000,000)이 주어진다. 그 다음 줄에는 1, 2, 3, 4, 5, 6번 돼지가 첫 날 먹었던 식사의 양이 빈 칸을 사이에 두고 차례대로 주어진다. 첫째 날에 각 돼지가 먹는 사료의 양은 100이하의 자연수이다.

 

출력

각 테스트 데이터에 대해, 6마리 돼지의 요구를 모두 들어줄 수 없게 되는 날이 몇 번째 날인지 출력한다.

 

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

 

돼지 1번이 첫 날 먹은 양을 a라고 하자. 
a 가 늘어나는 비율을 구하면 다른 돼지가 첫 날 먹은 양도 얼마나 더 늘었는지 알 수 있다.

두 번째 날에는 1번 돼지, 좌,우,맞은편 돼지까지  a를 줘야하므로 a정도의 양이 4배 필요하다.
세 번째 날에도 4배가 필요해져서
a는 날이 갈 수록 4배씩 필요해진다.

모든 돼지가 먹은 양이 매일 4배씩 늘어난다.

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    a = eval("+".join(sys.stdin.readline().split())) # 첫 날 돼지 6마리가 먹은 총 양
    i = 1
    while 1:
        if a > n:
            print(i)
            break
        a *= 4 # 4배
        i += 1

 

예제 입력 1 복사

2
21
1 2 3 4 5 6
21
1 2 3 4 5 7

예제 출력 1 복사

2
1