그리디는 이론만 보면 참 간단한 알고리즘이다.
현제 상황에서 최적화된 답을 고르면 되기 때문이다.

하지만 이러한 선택이 바로 보인다면 상관없겠지만
2번, 3번의 연산 앞을 봐야한다면 상당히 힘들 것이다.

High Score

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 253 81 58 33.143%
문제
Mårten and Simon enjoy playing the popular board game Seven Wonders, and have just finished a match. It is now time to tally the scores.

One of the ways to score in Seven Wonders is through the use of Science. During the game, the players may collect a number of Science tokens of three different types: Cog, Tablet, and Compass. If a player has a Cogs, b Tablets and c Compasses, that player gets a2 + b2 + c2 + 7 · min(a, b, c) points.

However, the scoring is complicated by the concept of Wildcard Science tokens. For each Wildcard Science token a player has, she may count that as one of the three ordinary types of Science tokens. For instance, the first player in Sample Input 1 has 2 Cogs, 1 Tablet, 2 Compasses, and 1 Wildcard Science, so could thus choose to have the distributions (3, 1, 2),(2, 2, 2) or (2, 1, 3) of Cogs, Tablets and Compasses, respectively. The possible scores for this player are then 32 + 12 + 22 + 7 · 1 = 21, 22 + 22 + 22 + 7 · 2 = 26 and 22 + 12 + 32 + 7 · 1 = 21 depending on how the Wildcard Science is assigned. Thus, the maximum score for this player is 26.

Given the number of tokens each player in the game has, compute the maximum possible score that each of them can achieve if they assign their Wildcard Science tokens optimally.

입력
The input consists of:

One line with an integer n (3 ≤ n ≤ 7), the number of players in the game.
n lines, each with four integers a, b, c, d (0 ≤ a, b, c, d ≤ 109), giving the number of Cog, Tablet, Compass, and Wildcard Science tokens of a player.
출력
For each player, in the same order they are given in the input, output the maximum score the player may get.

마라톤 문제이다. 일정 수준 넘어가면 언어선택이 안된다고 한다..
대충 문제를 살펴보면

a , b , c , d 가 주어지고
a^2 + b^2 + c^2 + 7*min(a,b,c) 의 최대값을 구하라는 것이다.
단, d의 값은 a,b,c에 자유롭게 분배 가능하다.

그럼 우리는 우선 생각해야 할 것이 왜 7*min(a,b,c)가 나오는가? 이다.
잠시 생각해보자. 왜 하필이면 7일까?

그것은 제곱수의 간격에 있다.

1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16

위 계산을 보면 3->4로 숫자가 증가할때, 제곱수는 7이 증가한다는 것을 알 수 있다. 그러니까, 이 사실을 가지고 위의 문제를 다시 읽었을때, d를 그냥 막 더해버리면 a,b,c,d가 작을때, 즉 7*a가 끼치는 영향이 클때 반례가 나와버린다는 것이다.

다음 예시를 보자.

a,b,c,d = [1,1,0,2]

case1
a,b,c,d = [3,1,0,0] => 계산값 : 10

case2
a,b,c,d = [2,1,1,0] => 계산값 : 13

위의 반례가 보이는가?
숫자가 작을때, 하나의 숫자에 d를 모두 더하는것 보다
7*a의 크기를 키우는것이 전체 계산값이 증가했다.

반례가 하나 더 있는데, 그것은 d의 값이 충분히 클때 이다.

a,b,c,d = [0,0,0,300]

case1
a,b,c,d = [100,100,100,0] => 계산값 : 30700

case2
a,b,c,d = [300,0,0,0] => 계산값 : 90000

그러니 d의 숫자가 커지면 하나의 숫자에 다 더하는게 계산값이 가장 커진다.
이를 유의하면 다음과 같은 설계를 할 수 있다.

• max(a,b,c) > 3 이라면 가장 큰 수에 d를 더함
• max(a,b,c) <=3 이라면 숫자를 골고루 분배
• 모든 수를 다 계산하면 시간초과가 발생.
• 그리고 d가 충분히 크다면 하나의 숫자에 모두 더함

위를 반영한 전체 코드는 다음과 같다.

from collections import deque
N = int(input())

def cal(a,b,c):
    return a**2 + b**2 + c**2 + 7 * min(a, b, c)

ans = []
for i in range(N):
    a , b , c , d = map(int,input().split())
    while d>0:
        if d <10:
            deq = deque()
            deq.append([a,b,c,d])
            max_num = [0,0,0,0,0]
            while deq:
                A,B,C,D = deq.popleft()
                if max_num[4] < cal(A,B,C):
                    max_num = [A,B,C,D,cal(A,B,C)]
                if D > 0:
                    deq.append([A+1,B,C,D-1])
                    deq.append([A,B+1,C,D-1])
                    deq.append([A,B,C+1,D-1])
            a = max_num[0]
            b = max_num[1]
            c = max_num[2]
            d = max_num[3]
        else:
            if a >= b and a >= c:
                a += d
            elif b >= a and b >= c:
                b += d
            else:
                c += d
            d = 0
    ans.append(a**2 + b**2 + c**2 + 7 * min(a, b, c))

for i in ans:
    print(i)

여담

플래티넘을 찍었지만 뉴비는 벗어나지 못한거 같다.
이번에 풀었던 문제가 이상하게 반례도 있고 해법을 못찾아서 한참 해매다가 푼 사람 목록을 보았더니..

이런사람들이 문제 난이도 평가에 실버1을 줬다..
아직 나는 한참 멀었나보다.
근데 애초에 루비랑 내가 비교가되는게 맞나 싶다