그리디14 [그리디 #15] BOJ 1700 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 1차 시도 너무 간단하게 생각했다. 뒷 부분 중 가장적게 사용되는 것을 뽑는 것으로 진행해버렸다. 당연히 반례가 존재한다. 3 15 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3 위 반례에서 3과 2를 꼽고나서 1이 나왔을 때, 3이 2보다 많이 사용되므로 2를 뽑게된다.. 정답 "가장 나중에 사용되는 것을 우선적으로 뽑자!" 라는 것을 다시 생각해보았다. 나중에 사용된다는 것이 현재 꼽아.. 2024. 2. 16. [그리디 #14] BOJ 16953 - A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A ㅁ 인 경우에 정답을 피해갈 수 있다. 여기서 착안한 것이 b를 기준으로 해보자는 것. b를 기준으로 끝이 1이면 띄어 버리면 된다. 근데 여기서도 문제가 존재한다. 예를 들어 11 33을 보자. 정답은 당연히 -1이다. 그러나 33/2를 하면 소수부분이 날라가기 때문에, 2로 나누어 떨어질때만 /2 를 하도록 설정 정리하자면. 1) if(b%10 == 1) { b/=10 } 2) else if(b%2 == 0) { b/=2.. 2024. 2. 14. [그리디 #13] BOJ 13164 - 행복 유치원 https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 1차 시도 예제를 토대로 알고리즘을 설계했다. 1. 가장 큰 것을 하나로 만듬 2. 두 개씩 묶는 것이 무조건 이득 위 알고리즘에는 크나큰 실수가 있다. 5 2 1 5 6 7 8 라는 반례가 존재한다. 조의 개수 K가 커지면 위의 알고리즘이 성립하지만, K가 적은 수일 경우 적용되지 않을 수 있다. { 1 } , { 5 6 7 8 } -> 정답: 4 { 1 5 6 7 } ,.. 2024. 2. 14. [그리디 #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. [그리디 #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. 이전 1 2 3 다음
