33661 백준(BOJ) 3366 수열 줄이기(Python) 스택 문제. reduce 연산의 비용의 합을 최소로 하기 위해서는, 수열의 최솟값부터 reduce를 해주면 된다. 어짜피 reduce를 진행해나가게 되면 어떤 수 양 옆에 존재하는 수는 절대 작아질 수 없기 때문이다. 즉, 어떤 수가 수열의 최솟값인 경우가 그 수에 대해 reduce를 진행했을 때 reduce의 최솟값인 것이다. 이를 이용하면 쉽게 문제를 해결할 수 있다. 수열의 처음부터 내림차순으로 stack에 수를 집어넣다가 현재 집어넣는 수가 내림차순을 만족하지 않는 경우 reduce를 진행하면 된다. 왜냐하면, 내림차순을 만족하지 않는 수가 등장하게 되면 그 순간 스택의 수들 중 스택의 맨 위에 위치한 수(a)가 현재까지 확인한 부분수열의 최솟값이고, 위에서 설명한 알고리즘대로 문제를 해결하면 되.. 2022. 7. 16. 이전 1 다음