본문 바로가기

백준/그리디

 (26)
[APIO] 백준 1150 - 백업 https://www.acmicpc.net/problem/1150 전개 언뜻 보면 가장 짧은 거리만 취하면 되는 그리디로 보인다. 하지만 문제의 예제에서는 가장 짧은 경우인 회사 2 - 회사 3을 선택하고 있지 않다. 만약 {2, 3}를 택하게 되면 {1, 2}와 {3, 4}를 쓰지 못하게 되고 여기서 괜찮은 경우가 있을 수 있으므로 완벽한 최적해를 찾을 수 없다. 이를 거꾸로 보면 {2, 3}을 포기하면 {1, 2}와 {3, 4}를 챙길 수 있다는 말이 된다. 우리는 여기서 다음과 같은 전략을 생각해볼 수 있다. 일단 값이 작은 쌍을 가져가되, 상황에 따라 해당 쌍을 버리고 옆의 두 쌍을 취하기 그러면 예제를 완벽히 설명할 수 있다. 1. 일단 {2, 3}을 가져간다. 그러면 한 쌍이 연결된다. 2. ..
백준 16225 - 제271회 웰노운컵 https://www.acmicpc.net/problem/16225 아이디어 우리는 저 숫자들을 괄호 집합으로 볼 것이다. 그러면 높은 합을 만들어내면서도 올바른 괄호 집합을 유지해야 하는 문제로 바뀐다. 문제를 보면 "내가 두 문제를 고르면 Etacoder Plus는 당연히 더 높은 B값을 가지는 문제를 가져갈 것이다."로 인해 B가 가장 높은 값은 Etacoder가 가져가고 B가 제일 낮은 값은 내가 가져감을 이해할 수 있다. 잘 이해가 가지 않는다면 곰곰히 생각해보자. 어떻게 해서든 내가 B가 제일 높은 값을 가져갈 수 없다는 사실을 깨우치면 이해할 수 있다. 그러면 주어진 pair 수열을 B의 오름차순으로 정렬하고 내가 가져가는 문제를 여는 괄호라 하고 상대가 가져가는 문제를 닫는 괄호라고 할 때..
백준 1437 - 수 분해 https://www.acmicpc.net/problem/1437 아마 이 글에 들어왔으면 같은 생각을 하고 있었을지도 모른다. "2 끼리 빼고 남는 거 3 만드는 게 최적해 아닌가?" 놀랍게도 아니다. 3씩 빼서 세제곱을 먹이는 게 더 커진다. 조금만 생각해도 제곱 증가량 < 세제곱 증가량인걸 눈치챌 수 있다. 아뿔싸! 따라서 3씩 빼다가 나머지가 1이면 하나를 4로 만들고, 나머지가 2면 2를 하나 만들어주는 식으로 전개한 뒤에 계산하면 최적해가 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 4..
백준 20370 - 공정한 게임 https://www.acmicpc.net/problem/20370 발상과 사전 작업 문제의 상황과는 반대로 BOT_10에게 이득인 값들을 먼저 배정한다. 그다음부터 BOT_6584가 BOT_10이 가진 값을 일부 강탈하면서 요구하는 답을 최대화시킬 것이다. 따라서 BOT_10에게 큰 값을 주도록 B의 내림차순으로 주어진 수열을 정렬하도록 한다. A는 정렬 기준을 신경 쓰지 않아도 된다. 무엇을 강탈할까? BOT_10이 가진 값을 강탈하기로 했는데 무엇을 강탈할지 잘 모르겠다. 문제를 다시 보면 [(자신이 고른 캐릭터들의 숙련도 합 - 상대방이 고른 캐릭터들의 숙련도 합)]을 최대화해야 하므로 BOT_6584의 기준으로 BOT_6584의 숙련도 합 - BOT_10의 숙련도 합이 된다. 우리는 다음과 같은..
백준 23354 - 돌 가져가기 https://www.acmicpc.net/problem/22354 해당 포스트에서는 공식 풀이에서 명확하지 않을 수 있는 부분에 부연 설명을 달았다. 먼저 보고 오도록 하자. x 양 옆 중 하나는 최적해가 아니라고? 아마 풀이에서 가장 이해가 되지 않는 부분일 수 있다. 얼핏 생각하면 저 하이라이트 한 부분에서는 다음과 같은 경우에 의해 반례가 있을 수도 있다는 생각을 할 수 있다. WBWBWBWBW 1 5 5 5 1 1 1 1 1 이는 최적으로 가져가야 할 돌들이 한 곳에 뭉친 경우이다. 여기서 세 번째 돌을 취하려 하면 두 번째나 네 번째 돌을 버리란 말이냐!? 와 같은 의구심이 생길 수 있다. 끝부터 가져가자 조금만 더 생각하면 답은 의외로 쉽다. 가장 끝부분인 4번째 돌부터 내부로 향하면 된다...

티스토리툴바