그리디
-
[BOJ] 20365 블로그2 - C++개발/알고리즘 & PS 2024. 4. 7. 13:24
https://www.acmicpc.net/problem/20365 20365번: 블로그2neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한www.acmicpc.net 아이디어번갈아가며 나오는 색을 가장 적은 횟수로 칠해야 한다. 색을 다시 덧칠할 수 있음을 이용하면 된다. 연속해서 같은 색을 칠하는 부분을 하나로 생각하고 총 $m$개의 구역으로 나눌 수 있다고 하자. 빨간색과 파란색은 $\frac{m}{2}$내지 $\frac{m}{2} + 1$개의 구역을 가질 것이다. 첫 시도에 둘 중 많은 색을 칠하고 $\frac{m}{2}$번의 색을 칠하는 경우가 최소가 된..
-
[BOJ] 11508 2+1 세일 - C++개발/알고리즘 & PS 2024. 4. 1. 13:16
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두www.acmicpc.net아이디어최소한의 값을 지불하려면 무료로 받는 제품의 가격을 최대한 크게 만들어야 한다. 다만, 무료로 받을 수 있는 제품은 3개 중 가장 싼 제품이기에 다른 두 제품이 비쌀수록 큰 할인을 받을 수 있다. 따라서, 내림차순으로 정렬한 후 3개씩 묶어 사면된다. 코드#include #include using namespace std;int main() { cin.tie(nullptr); ..