알고리즘51 [그리디 #10] BOJ 20115 - 에너지 드링크 https://www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 구현에서 문제가 발생;; 접근 방법 a = a + (b / 2) 을 통해 마지막 남은 드링크의 양이 최대가 되어야 한다. b/2되는 부분이 최소가 되어야 버려지는 양이 적기 때문에 a: 양이 많은 것 b: 양이 가장 적은 것 이런 식으로 생각함. 1차 시도 vector 2개 v1과 v2를 만듬. v2에 가장 큰 것 + (가장 작은 것 / 2)를 넣고, 추후 나머지도 넣는 방식으로 진행함. sort.. 2024. 2. 12. [그리디 #9] BOJ 11508 - 2+1 세일 https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 접근 방법 3개씩 묶어서 구매할 때, 가장 싼 제품을 무료로 준다는 것이 핵심이다. 금액을 최소로 만들기 위해서는 가장 싼 제품으로 가격이 꽤 나가는 제품이 선정되어야한다. 이를 위해선 나머지 두 제품이 가장 비싼 제품으로 선정되어야 한다는 것이다. 다시 말해, 금액을 내림차순으로 정렬 후, 3개씩 묶어서 구매하면 된다. 정석적인 그리디 접근법으로 다가가면 쉽게 풀 수 있는 문제이다. .. 2024. 2. 11. [그리디 #8] BOJ 1758 - 알바생 강호 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 접근 방법 그리디의 정석으로 풀 수 있는 문제 중 하나이다. 이 문제에서 주문금액 - (등수 - 1)의 공식을 이용해 최고의 팁을 받는 것이 문제의 끝이다. 별다른 조건은 없기 때문에 주문금액이 가장 큰 손님부터 받게되면 팁을 최대로 챙길 수 있다. 쉽게 접근할 수 있는 문제라고 생각한다. 구현 시, N이 최대 100,000, 팁이 100,000을 넘을 수 있기 때문에 타입 선정.. 2024. 2. 11. [그리디 #7] BOJ 13305 - 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 접근 방법 예제 1을 살펴보자. 여기서 중요한 점을 체크해봤다. 1. 첫번째 도시에선 무조건 기름을 구입해야한다. 2. 마지막 도시의 기름값은 무시한다. 3. 현재 도시에서 다음 도시들 중 현재 도시의 기름값보다 싼 도시까지 가는 기름만 구매한다. (2에서 4를 거쳐 1로 가는 과정에서 2보다 싼 도시까지가는 거리의 기름을 산다.) 예를 들어 2 4 5 1 3 이런 도시가 있다고할 .. 2024. 2. 10. [그리디 #6] BOJ 1343 - 폴리오미노 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 접근 방법 매우 간단한 그리디 문제이다. 저번에 풀었던 거스름돈 문제와 같은 풀이로 해결이 가능하다. https://parvegoongame.tistory.com/115 [그리디 #5] BOJ 14916 - 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 접근 방법 간단한 그리디 문제이다. 5원과 2원 뿐이기 때문에 5원을 빼야하는 경 meteorfi.. 2024. 2. 10. [그리디 #5] BOJ 14916 - 거스름돈 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 접근 방법 간단한 그리디 문제이다. 5원과 2원 뿐이기 때문에 5원을 빼야하는 경우와 2원을 빼야하는 경우를 잘 생각해보자. 5원이 빠질 경우는 5원을 뺐을때, 나머지가 5으로 나누어떨어지거나 2로 나누어떨어지만 5원으로 결정. 2원이 빠질 경우는 2원을 뺐을때, 나머지가 2로 나누어 떨어지면 2원으로 결정. 코드 #include #include #include using namespace std; int n; int rest; int cnt; int main() { ios::sync_with_stdio(false).. 2024. 2. 9. 이전 1 ··· 4 5 6 7 8 9 다음
