본문 바로가기

분류 전체보기172

[그리디 #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.
[그리디 #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.

티스토리툴바