그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/17299왠지 모르게 골드 3이라는 난이도 때문에 예전에 풀 의지를 느끼지 못했던 문제인데, 차근히 풀어보니 그렇게 어려운 문제는 아닌 스택 문제이다.문제 이해길이가 N인 수열이 있을 때 i번째 원소를 x원소라고 해보자.이 때, '자기랑 같은 숫자가 배열 안에 등장한 횟수'가 F(x)의 값이다.[1 1 2 3 4 2 1]이라는 배열이 있다면 x=1일 때, F(1) = 3이라는 것이다. (1이 배열에서 3번 등장했으므로)그렇다면 이 때 '오등큰수'는 배열에서 자기보다 오른쪽에 있으면서 F(x) 값이 자기보다 큰 최초의 x이다.만약 그러한 x가 없다면, 그 수의 '오등큰수'는 -1이 된다.위와 같은 조건을 가질 때, 배열의 모든 원소의 '오등큰수'를 ..

문제 이해중복 가능한 정수가 나열된 길이가 N인 수열이 있을 때, 해당 수열에서 범위 l, r을 잡아서 그 범위 안에서 가장 작은 수를 전부 삭제할 수 있을 때, 최소 몇 번의 삭제 연산이 필요한지 계산하는 문제이다.여기서 중요한 것은 N과 함께 입력되는 K라는 입력값인데, 이 K값만큼 원하는 수들을 원하는 수로 변경시킬 수 있다.예를 들어 K = 1인 경우, [1 2 1]이라는 배열을 [1 1 1]로 변화시켜 1번의 삭제 연산으로 배열의 수를 전부 삭제할 수 있는 것이다. 문제 해설이 문제에서 주의할 점은 배열 안의 수가 배열된 순서가 큰 의미가 없다는 것이다.결국에는 모든 수를 삭제하려면 최소한남아있는 수의 종류만큼 삭제 연산이 필요하기 때문이다.즉, K를 이용하여 남아있는 수의 종류를 최소화하는게 ..