공부하자 동진아

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네 번째 칸 (5)를 밟았으면, 2행의 네 번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return 하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네 번째 칸 (5), 2행의 세 번째 칸 (7), 3행의 첫 번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수

• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.

• 점수 : 100 이하의 자연수

입출력 예

코드

def solution(land):
    answer = 0
    N = len(land)
 
    for i in range(0,N-1):
        land[i+1][0] += max(land[i][1],land[i][2],land[i][3])
        land[i+1][1] += max(land[i][0],land[i][2],land[i][3])
        land[i+1][2] += max(land[i][0],land[i][1],land[i][3]) 
        land[i+1][3] += max(land[i][0],land[i][1],land[i][2])
   
    answer = max(land[N-1])

    return answer

풀이 방법

  • 동적 계획법(Dynamic Programming)을 사용하여 문제를 풀었습니다.

  • n번째 행에 값들에 n-1번째 행들의 값들 중 해당 열 값을 제외한 나머지 값의 최대값을 더해줘 쌓여가는 방식으로 풀었습니다.

  •  i = 0 일 때

|  1 |  2 |  3 |  5 |
| 10 | 11 | 12 | 11 |
|  4 |  3 |  2 |  1 |

  • i = 1 일 때

|  1 |  2 |  3 |  5 |
| 10 | 11 | 12 | 11 |
| 16 | 15 | 13 | 13 |

  • for문이 다 돌고 마지막 행에서 최대값을 반환한다.

answer = max(land[N-1])

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)

• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)

• A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수

• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)
이 경우가 최소이므로 10을 return 합니다.

코드

def solution(A,B):
    answer = 0
    A = sorted(A)
    B = sorted(B)[::-1]
    
    for i in range(len(A)):
        answer += A[i] * B[i]
            
    return answer

풀이 방법

  • A에 가장 큰 값과 B의 가장 작은 값을 곱해서 더해가면 누적 값이 최소가 나온다.

  • A를 오름차순으로 정렬하고, B를 내림차순으로 정렬하고 같은 위치에 있는 배열의 수를 곱하는 방식으로 풀었습니다.

[1, 4, 2] -> [1, 2, 4]
[5, 4, 4] -> [5, 4, 4]

def solve(a):
    ans = sum(a)
    return ans

c = int(input())

for i in range(c):
    count = 0
    answer = 0
    score = list(map(int, input().split()))
        
    avg = sum(score[1:]) / score[0]
    for x in score[1:]:
        if x > avg:
            count += 1
            
    answer = (count / score[0]) * 100
    
    print('%.3f' % answer + "%")