Jonyo Programming

[BOJ 11003(P5)리뷰] 문제는 매우 간단하다. (하지만 푸는건 간단하지 않음 ..) N개의 수와 정수 L이 주어진다. 각각의 원소마다 자신의 앞과 자신의 앞을 포함하여 L개의 원소 중 최솟값을 출력하면 된다. 예를들어 N=8이고 [1,5,2,3,6,2,3,7] L이 3이라면 1 -> 최솟값 : 1 1,5 -> 최솟값 : 1 1,5,2 -> 최솟값 : 1 5,2,3 -> 최솟값 : 2 2,3,6 -> 최솟값 : 2 3,6,2 -> 최솟값 : 2 이런식으로 최솟값을 출력하면된다. 창틀을 정해놓고 그 창틀을 조금씩 이동하는것처럼 보이기도 하여 슬라이딩 윈도우라고도 한다. 일단 각각의 원소마다 자신의 앞에 있는 수를 탐색하는 O(N^2)으로는 절대 안풀리고 힙이나 BST를 이용한 O(NlogN)으로도 ..

[BOJ 1715(G4) 리뷰] 처음에 문제를 어떻게 풀어야 할지 고민했다. 이전에 이거랑 비슷한 유형의 문제 DP문제를 풀다 포기한적이 있었는데 이문제는 다행히 DP문제가 아니라 풀수있었다. 카드를 비교할때마다 그 값들이 더해지고 최종적으로 카드가 1묶음이 남을때 그 더해지는 값의 최소값을 구해야 한다. 인풋이 10만이기에 모든 경우를 탐색하는 경우 시간초과가 나게 된다. 따라서 방법을 탐색해야하는데 문제의 조건을 천천히 생각해보자. 일단 이 문제의 최종 목표는 카드를 1묶음으로 만드는것이다. 따라서 카드 두개를 합치는 과정은 계속 되야한다. 그리고, 카드를 합치는 과정에서 비용이 발생한다. 이미 존재하는 카드 묶음의 값을 바꿀수는 없으니 우리는 카드를 합치는 과정에서 발생하는 비용을 최소화 해야 한다..