(LeetCode) Pizza With 3n Slices with Python

There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:

• You will pick any pizza slice. (당신은 어떤 피자조각을 고를 수 있다.)
• Your friend Alice will pick next slice in anti clockwise direction of your pick. (너의 친구 엘리스는 당신의 선택의 반시계 방향으로 다음 조각을 고른다.) 
• Your friend Bob will pick next slice in clockwise direction of your pick. (너의 친구 밥은 당신의 선택의 시계방향으으로 다음 조각을 고른다.)
• Repeat until there are no more slices of pizzas. (피자 조각이 더 이상 없을 때까지 반복한다.)

Sizes of Pizza slices is represented by circular array slices in clockwise direction.

(피자 조각의 크기는 시계방향의 원형 배열 조각으로 표시된다.)

Return the maximum possible sum of slice sizes which you can have.

(가질 수 있는 슬라이스 크기의 가능한 최대 합계를 반환한다.)

 

 

Example 1:

예시 1

 

Input: slices = [1,2,3,4,5,6]
Output: 10
Explanation: Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively.
Then Pick slices with size 6, finally Alice and Bob will pick slice of size 2 and 1 respectively. Total = 4 + 6.

 

Example 2:

예시 2

Input: slices = [8,9,8,6,1,1]
Output: 16
Output: Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.

 

 

Example 3:

 

Input: slices = [4,1,2,5,8,3,1,9,7]
Output: 21

 

Example 4:

 

Input: slices = [3,1,2]
Output: 3

 

Constraints:

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000

 

(Hint1)

By studying the pattern of the operations, we can find out that the problem is equivalent to: Given an integer array with size 3N, select N integers with maximum sum and any selected integers are not next to each other in the array.

 

: 연산 패턴을 연구함으로써 문제가 다음과 같다는 것을 알 수 있습니다. 크기가 3N 인 정수 배열이 주어지면 최대 합을 가진 N 개의 정수를 선택하고 선택한 정수는 배열에서 나란히 있지 않습니다.

 

(Hint2)

The first one in the array is considered next to the last one in the array. Use Dynamic Programming to solve it.

 

: 배열의 첫 번째 항목은 배열의 마지막 항목 옆에있는 것으로 간주됩니다. 이를 해결하기 위해 동적 프로그래밍을 사용하십시오.

 

💯 Solution

동적계획법 (Dynamic Programming)기술을 이용해서 코드를 작성해보자.

 

class Solution:
    def maxSizeSlices(self, slices):
 
        # ex) slices = [1,2,3,4,5,6] / k=6
        # 3으로 나눈 만큼 반복하기 때문에 3으로 나눔
        k=len(slices)//3
 
        # 주어진 배열을 [:-1] 제일 뒤에 값을 제거 / 주어진 배열을 [1:] 첫번째 값을 제거 해서 dp에 돌린다.
        return max(self.dp(slices[:-1], k), self.dp(slices[1:], k))
 
    #동적 계획법 적용
    def dp(self, slices, k):
 
        # ex) array = [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
        array = [[0]*(k+1) for i in range(len(slices)+1)]
        #print(array)
        for i in range(1, len(slices)+1):
            #print('i는:',i)
            for j in range(1, k+1):
                #print('j는:', j)
                if i==1:
                    array[i][j] = slices[i-1]
                    continue
                array[i][j] = max(array[i-2][j-1] + slices[i-1], array[i-1][j])
                #print(array)
        return array[-1][-1]
 
 
a=[1,2,3,4,5,6]
test = Solution()
test.maxSizeSlices(a)
 

 

출력값

[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
i는: 1
j는: 1
j는: 2
i는: 2
j는: 1
[[0, 0, 0], [0, 1, 1], [0, 2, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
i는: 3
j는: 1
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 0], [0, 0, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 4], [0, 0, 0], [0, 0, 0]]
i는: 4
j는: 1
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 4], [0, 4, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 4], [0, 4, 6], [0, 0, 0]]
i는: 5
j는: 1
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 4], [0, 4, 6], [0, 5, 0]]
j는: 2
[[0, 0, 0], [0, 1, 1], [0, 2, 2], [0, 3, 4], [0, 4, 6], [0, 5, 8]]
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
i는: 1
j는: 1
j는: 2
i는: 2
j는: 1
[[0, 0, 0], [0, 2, 2], [0, 3, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
i는: 3
j는: 1
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 0], [0, 0, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 6], [0, 0, 0], [0, 0, 0]]
i는: 4
j는: 1
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 6], [0, 5, 0], [0, 0, 0]]
j는: 2
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 6], [0, 5, 8], [0, 0, 0]]
i는: 5
j는: 1
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 6], [0, 5, 8], [0, 6, 0]]
j는: 2
[[0, 0, 0], [0, 2, 2], [0, 3, 3], [0, 4, 6], [0, 5, 8], [0, 6, 10]]

Process finished with exit code 0