[python] 백준 30960번 조별과제

조별 과제 

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

 

[풀이]

시도 1

3명 조의 어색함 값을 다 구하고 2명 조 어색함 값을 모두 구해 적절히(?) 더한다

예를 들어 아래와 같은 값이 입력됐다 가정했을때,

7
20 10 9 11 3 18 1

 

우선 정렬을 해주면

1

3

9

10

11

18

20

1 3 9 10 11 18 20 이 된다.

 

여기서 세명 조 편성의 경우는

A 1 3 9

B 9 10 11

C 11 18 20

이렇게 세가지일 것이다.

(다른 경우는 어색함의 값을 최소화하는데에 불리함)

A조의 어색함의 값은 9-1 = 8

B조는 11-9 = 2

C조는 20-11 = 9 가 된다.

 

각각의 값을 리스트에 넣고 L2 = [8,2,9]

for i in range(0,n-2,2):
    a = L[i+2]-L[i]
    L2.append(a)

 

2명의 조의 나올 수 있는 어색함의 값을 모두 리스트에 넣어준다.

L3 = [2,6,1,1,7,2] 가 될것이다.

for i in range(0,n-1):
    L3.append(L[i+1]-L[i])

 

A조가 편성됐을 경우 나머지 10 11 / 18 20 의 어색함을 더해야하므로 L3[4]와 L[36]을 더하면 된다.

B조가 편성됐을 경우  1 3 / 18 20 의 어색함을 더해야하므로 L3[0]과 L3[6]을 더해야한다.

C조가 편성됐을 경우 1 3 / 9 10 의 어색함을 더해야하므로 L3[0]과 L3[2]을 더해야한다.

따라서 세명 조의 시작 인덱스 값(start)을 이용해서 L3에 해당하는 인덱스까지 반복하여 더하고자 했다.

k=0
for i in range(len(L2)):
    sum = L2[i]
    start = i+k
    for j in range(0,start,2):
        sum += L3[j]
        
    for j in range(start+3,n,2):
        sum += L3[j]
        
    k += 1
    sol.append(sum)

 

 

그런데 반복문을 중첩해서 그런지 시간 초과가 발생했다.

 

따라서 아래와 같은 방법으로 시도하여 해결했다.

 

시도2

중첩 반복문을 이용하지 않고 해결해야했기 때문에 누적합을 이용했다.

 

먼저 왼쪽에서 부터 두명씩 잘랐을 때 생성되는 어색함의 합은

1

3

9

10

11

18

20

0

2

0

3

0

10

0

left 🔼

 

위와 같이 2( .   ),3( .   + .   ),10 ( .   + .   + .   ) 이 될것이다.

 

그리고 오른쪽에서부터 두명씩 잘랐을 때 생성되는 어색함의 합은

1

3

9

10

11

18

20

0

0

9

0

3

0

2

right 🔼

 

위와 같이 뒤에서 부터 합을 계산하면 9( .   + .   + .   ) , 3( .   + .   ), 2 ( .   ) 가 될것이다.

 

이렇게 리스트 두개를 만들어두고 

세명의 조가 1,3,9일때는 (10 11), (18 20)의 차의 합을 더해야하므로 right리스트의 4번 값만 더해주면 된다.

1

3

9

10

11

18

20

세명조의 어색함 값 : 9 - 1 = 8

두명 조의 어색함 값 : 3 (left) + 0 (right)

총 어색함 :  8 + 3 + 0 = 11

 

 

그리고 세명의 조가 9,10,11일때는 (1 3), (18 20)의 차의 합을 더해야하므로 right리스트의 6번 값과 left리스트의 1번 값을 더해주면 된다.

1

3

9

10

11

18

20

세명조의 어색함 값 : 11 - 9 = 2

두명 조의 어색함 값 : 2 (left) + 2 (right)

총 어색함 : 2 + 2 + 2 = 6

 

 

또 마지막 세명의 조가 11, 18, 20일때는 (1 3), (9 10)의 차의 합을 더해야하므로 left리스트의 4번 값만 더해주면 된다.

1

3

9

10

11

18

20

세명조의 어색함 값 : 20 - 11 = 9

두명 조의 어색함 값 : 3 (left) + 0 (right)

총 어색함 : 9 + 3 + 0 = 12

 

따라서 가장 최소값인 6이 최소의 어색함값의 합이 되는 것이다.

 

정답

import sys
input = sys.stdin.readline

n = int(input())
std = list(map(int, input().split()))


std.sort()

left = [0]*n
for i in range(1,n,2):
    left[i] = left[i-2] + std[i]-std[i-1]
    
right = [0]*(n+2)   #인덱스 범위 초과를 대비하여 n+2칸까지 생성
for i in range(n-1,1,-2):
    right[i] = right[i+2] + std[i]-std[i-1]

min_awk = 10**10
for i in range(0,n-1,2):
    awk3 = std[i+2]-std[i]
    awk2_left = left[i-1] if i>0 else 0
    awk2_right = right[i+4] if i+2 < n-1 else 0
    min_awk = min(min_awk, awk3+awk2_left+awk2_right)
print(min_awk)

 

이 문제를 파이썬으로 해결한 블로그가 많이 안보여서 푸는데에 굉장한 어려움이 있었다 ㅜㅜ