해설어떤 순서로 연산하더라도 전체 비용은 같으며, 정답은 ∑i=1NPi−min1≤i≤NPi\sum_{i=1}^{N}P_i-\min_{1\leq i\leq N}P_ii=1∑NPi−1≤i≤NminPi 이다. 수열을 한 번 읽으며 합과 최솟값을 구하면 된다. 시간 복잡도는 O(N)O(N)O(N), 추가 공간 복잡도는 O(1)O(1)O(1)이다.증명인접한 두 값 x,yx,yx,y를 min(x,y)\min(x,y)min(x,y)로 바꾸면 수열의 합은 x+y−min(x,y)=max(x,y)x+y-\min(x,y)=\max(x,y)x+y
