두 종류 물건을 특정 개수만큼 사면서 최소 가격에 사는 그리디 알고리즘

1. 문제 30022번: 행사 준비 (acmicpc.net) 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 2. 풀이 첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서, 이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고.. 아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 25.
• textsms

배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

1. 문제 25214번: 크림 파스타 (acmicpc.net) 25214번: 크림 파스타 각 $A_i$가 추가된 직후의 문제의 답 $N$개를 공백으로 구분하여 출력한다. www.acmicpc.net 2. 풀이 그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고, n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에, dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀? 새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고 최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고 A[i]가 최솟값이라면 최솟값을 갱신해준다 여기서 $i \leq j$인 i,j에 대하여 A[j..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 6. 18.
• textsms