본문 바로가기

📊알고리즘/BOJ101

[그리디 #11] BOJ 20300 - 서강근육맨 https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 접근 방법 중요한 점) 1. 근손실 M을 넘지 않도록 설정한다는 것. 2. 하루에 운동 기구를 2개씩 사용 3. 홀수 일이면 마지막 날은 1개만 사용 이를 종합하면 2개씩 짝지은 합이 최소가 되고, 홀수 일 경우 가장 큰 값을 혼자 남겨놔야 최소가 된다. 따라서, 알고리즘은 다음과 같다. 전제: 오름차순 혹은 내림차순으로 정렬 / 마지막 값을 비교 대상(res)으로 설정 i) 짝수일 경우. 가장 큰 것과 가장 작은 .. 2024. 2. 12.
[그리디 #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.

티스토리툴바