저도 답이 궁금합니다.
Input
4
5 -10 -10 5
출력
0
아시는분 있다면 풀이방법과 코드부탁드립니다!
저도 답이 궁금합니다.
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년 전
모 기업 테스트에 나온 문제인데 풀이 방법이 잘 떠오르지 않아 질문드립니다.
N명의 인원들이 원형 테이블을 둘러싸고 앉아있으며, 각 인원들은 하나의 점수값을 가지고 있다.
이러한 인원들을 천사와 악마 그룹으로 나누려고 한다. 천사와 악마는 각각 2개의 그룹으로 이루어져 있다. 즉, 천사그룹1과 천사그룹2 사이에는 반드시 한 명 이상의 악마그룹에 속하는 사람이 있어야 하며, 마찬가지로 악마그룹1과 악마그룹2 사이에는 반드시 한 명 이상의 천사그룾에 속하는 사람이 존재해야 한다. (원형 테이블이므로 양방향을 고려해야한다.)
이 때, (천사그룹의 점수의 합 - 악마그룹의 점수의 합)의 최댓값을 구하시오.
4<=N<=200000, 각각의 점수는 -10^9이상 10^9 이하의 값을 가진다.
테스트 케이스는 기억이 잘 안나는 점 양해부탁드립니다..!