출항사

하나의 수열이 주어집니다. 이 수열은 순환이 된다고 합니다. 이 수열에서 연속적인 부분수열을 뽑았을때, 부분 수열의 합으로 나올 수 있는 모든 숫자를 구하라고 합니다. 결국 '연속된 부분 수열의 총합'을 구하라는 말인데 여기서 바로 누적합 알고리즘을 떠올려볼 수 있죠. 누적합 배열을 psum이라고 정의했을때 [i~j]에 존재하는 수열의 총합은 psum[j] - psum[i-1]로 O(1)에 계산할 수 있습니다. 그리고 이를 이용하면 O(N^2)에 모든 부분 수열을 계산할 수 있습니다. 이제 나올 수 있는 값들의 총 개수를 구해야 하는데, 간단하게 set으로 관리하면 총 시간복잡도는 O(N^2logN)이 소요됩니다. 하지만 아직 고려하지 않은 것이 있죠. 바로 수열이 순환할 수 있다는 조건입니다. 이 조건..

문제의 핵심은 상자의 묶음을 찾는 것이고, 이중 가장 큰 2개의 상자 묶음을 찾아 최댓값을 구해야 합니다. 상자의 개수가 100개이기 때문에 만들어질 수 있는 모든 상자 묶음을 찾아도 효율성 측면에서 문제가 되질 않습니다. 따라서 모든 상자의 묶음을 찾아주면 됩니다. 저는 상자 A -> 상자 B로 계속 이동하는 재귀 문을 작성해서 상자의 묶음을 찾았습니다. 한 가지 주의사항이 있는데요, 바로 전체 상자 묶음이 1개인 경우 점수가 0이라는 점입니다. 예를 들어 1, 2, 3, 4, 5, 6, 7과 같이 상자가 배치된 경우에 말이죠 이 부분은 아주 간단하게 처리할 수 있습니다. 모든 상자 묶음의 개수를 구할때마다 벡터에 넣고, 마지막으로 이 벡터에 0을 넣어줍니다. 벡터를 내림차순으로 정렬합니다. 그리고 우..