pinevienna blog

프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 쉬운 문제지만 비효율적으로 풀면 실행 시간만 반나절이다 priority_queue를 사용하여 풀 수 있음 priority_queue는 큐 안의 원소를 내림차순으로 정렬하기 때문에 입력받은 값과 priority_queue의 top을 비교하면 됨 입력받은 문서의 중요도를 저장할 queue는 pair로 선언하여 first에는 중요도를 second에는 몇 번째 입력값인지 저장해준다 queue.front().first ..

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 문제 ex) 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원 P1부터 PN까지 어떻게 사야지 가장 비싸게 살 수 있는지 순차적으로 구하면 된다 카드 1장을 산다면 P1 : (DP[1] = P1) 카드 2장을 산다면 P2 또는 P1 두 개 : DP[2] = max(P2, P1 + P1) 카드 3장을 산다면 P3, P1 세 개, P2 + P1 → P1 두 개가 비싼지, P2 한 개가 비싼지는 DP2에 저장되어 있다 : DP[3] = max(P3, DP[2] + P1) 이걸 식으로 만들면 D..

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 문제 DP오랜만이라 가장 긴 어쩌구 문제를 풀어봤다.. 근데 헷갈리는거 실화인가.. ^^ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; int arr[1000], dp[1000]; int res = 1; cin >> n; for (int i = 0; i > arr[i]; dp[i] = 1; for (int j = 0; j

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 한다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딘다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건넌다. 이 경우 모든 트럭이 다리를 지나려면 최소 8초가 걸린다 입려되는 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 반환하는 문제! 다리에 먼저 진입한 트럭이 먼저 빠져나오므로 queue 구조로 볼 수 있다 하나하나 따로 생각해보자 - 대기하는 트럭이 다리 위로 올라갈 수 있다면 진입시킨다 : 다리 위에 있는 트럭 리스트 / 다리 위에 있는 트럭의 총..

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다 이제 순서대로 K번째 사람을 제거한다 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다 N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 문제 이런식으로 진행된다 queue는 원형이 아니기 때문에 front를 계속 back으로 보내주면서 계산해야한다 1. front를 back으로 k-1번 보내준다 2. k번째 값을 출력 후 pop 한다 이 과정을 queue.empty() = true 일 때 까지 반복하면 됨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..