백준25 BOJ 11779 - 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 접근 방법 1753 최단경로 문제에 경로까지 출력하는 짬뽕된 문제이다. 다익스트라를 이용하여 문제를 풀어보도록 하자. 기존 priority_queue를 이용한 코드에 경로를 저장하는 것이 이 문제의 핵심이다. 경로를 어떻게 지정할까 생각을 하다 최소신장트리에서 부모를 저장하는 방법을 사용해보기로 했다. 1. 부모를 저장할 parent[] 를 선언 (자기 자신으로 초.. 2024. 2. 21. [그리디 #12] BOJ 20365 - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 1차 시도 예제에 있는 문장을 보고 어그로(?)에 끌려 이상하게 접근을 했다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다. 위 문장에서 먼저 파란색으로 칠한 다는 것 때문에, 무조건 밑 바탕을 칠하고 가야한다고 생각했다. 따라서, 다음과 같은 알고리즘을 설계함. 1. 가장 많은 색을 바탕으로 깔고 들어간다.. 2024. 2. 13. [그리디 #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. [그리디 #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. [그리디 #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. 이전 1 2 3 4 5 다음
