ccdh97092   4년 전


모 기업 테스트에 나온 문제인데 풀이 방법이 잘 떠오르지 않아 질문드립니다.


N명의 인원들이 원형 테이블을 둘러싸고 앉아있으며, 각 인원들은 하나의 점수값을 가지고 있다.

이러한 인원들을 천사와 악마 그룹으로 나누려고 한다. 천사와 악마는 각각 2개의 그룹으로 이루어져 있다. 즉, 천사그룹1과 천사그룹2 사이에는 반드시 한 명 이상의 악마그룹에 속하는 사람이 있어야 하며, 마찬가지로 악마그룹1과 악마그룹2 사이에는 반드시 한 명 이상의 천사그룾에 속하는 사람이 존재해야 한다. (원형 테이블이므로 양방향을 고려해야한다.) 

이 때, (천사그룹의 점수의 합 - 악마그룹의 점수의 합)의 최댓값을 구하시오.

4<=N<=200000, 각각의 점수는 -10^9이상 10^9 이하의 값을 가진다.


테스트 케이스는 기억이 잘 안나는 점 양해부탁드립니다..!
 

yongseong97   4년 전

저도 답이 궁금합니다.

Input

4

5 -10 -10 5

출력

0

아시는분 있다면 풀이방법과 코드부탁드립니다!

천사그룹을 A라고 하고 악마그룹을 B라고 하면

1. 원형의 특성상 A B A B 혹은 A B A B A 혹은 B A B A 혹은 B A B A B 형태여야 하고

2. 천사그룹의 점수의 합을 최대화해야 (천사그룹의 점수의 합 - 악마그룹의 점수의 합)이 커지니

각각의 값을 a[1...n]이라고 하면

d1[i] = A 꼴에서 천사 그룹의 점수의 합의 최대

d2[i] = A B 꼴에서 천사 그룹의 점수의 합의 최대

d3[i] = A B A 꼴에서 천사 그룹의 점수의 합의 최대

d4[i] = A B A B 꼴에서 천사 그룹의 점수의 합의 최대

d5[i] = A B A B A 꼴에서 천사 그룹의 점수의 합의 최대로 정의했을 때

d1[i] = d1[i-1]+a[i]

d2[i] = max(d1[i-1],d2[i-1])-a[i]

d3[i] = max(d2[i-1],d3[i-1])+a[i]

d4[i] = max(d3[i-1],d4[i-1])-a[i]

d5[i] = max(d4[i-1],d5[i-1])+a[i] 로 계산해

max(d4[n], d5[n])을 구하고 비슷한 논리로

d1[i] = B 꼴에서 천사 그룹의 점수의 합의 최대

d2[i] = B A 꼴에서 천사 그룹의 점수의 합의 최대

d3[i] = B A B 꼴에서 천사 그룹의 점수의 합의 최대

d4[i] = B A B A 꼴에서 천사 그룹의 점수의 합의 최대

d5[i] = B A B A B 꼴에서 천사 그룹의 점수의 합의 최대로 정의해 식을 잘 세워서 max(d4[n], d5[n])를 구하면 되지 않나 싶습니다.

ccdh97092   4년 전

@BaaaaaaaaaaarkingDog


친절한 답변 감사드립니다 바킹독님 ㅎㅎ. 유튜브는 잘 챙겨보고 있습니다~!

댓글을 작성하려면 로그인해야 합니다.