devbelly

문제 www.acmicpc.net/problem/21233 알고리즘 greedy 풀이 12의 배수에 해당하는 연도에 포탈이 열립니다. 모든 선조들을 만나고 돌아올 때, 걸리는 가장 짧은 시간을 구하는 문제입니다. 포탈은 최대 $K$번 이용할 수 있습니다. 전형적인 그리디 문제입니다. 포탈을 사용해서 건너뛰어야하는 구간은 연도차이가 가장 큰 구간입니다. 각 선조들의 연도를 거쳐야만 하는 연도(12의 배수중 하나)로 바꿉니다. 예를 들어 35년 전에 존재하는 선조는 36년도 전에 열리는 포탈을 거쳐야만 (또는 더 이전의 포탈에서 시간이 흘러야만) 올 수 있습니다. 거쳐야하는 포탈을 골랐다면 각 포탈의 차이(A포탈의 시작과 B 포탈의 끝)를 담는 벡터를 만든 후, 정렬해서 가장 큰 것부터 $K-1$개를 제외해..

문제 www.acmicpc.net/problem/11963 알고리즘 greedy 풀이 2$N$개의 카드를 나누어 가져 게임을 진행할 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $N$/2 이전 라운드는 큰 수를 내는 사람이 이기고, 이후 라운드는 작은 수를 내는 사람이 이깁니다. 큰 수 게임에서 bessie가 이길 수 있는 카드들이 있을 때, 최대한 작은 수를 내야 나중의 라운드를 준비할 때 유리합니다. 이를 위해 큰 수 게임을 진행할 때, elsie카드들 중 큰 수부터 처리해 나갑니다. 작은 수 게임도 마찬가지 이유로 elsie카드들 중 작은 수부터 처리해 나갑니다. 이 때 큰 수게임 중 카드를 낼 때, 이길 수 있는 카드들 중에서 작은 카드를 내게 되면 작은 수 게임에서 불리해질 수 도 있습니..

문제 www.acmicpc.net/problem/8875 알고리즘 Greedy 풀이 무게와 크기가 있는 장난감 $T$개가 주어집니다. 장난감을 정리하기 위해 연약한 로봇 $A$개와 작은 로봇 $B$개가 주어질 때, 정리하기 위한 최소 시간을 구하는 문제입니다. 연약한 로봇은 장난감의 크기와는 상관없이 자기보다 무게가 덜 나가는 장난감을 정리할 수 있고 작은 로봇은 무게에 상관없이 자기보다 작은 장난감을 정리할 수 있습니다. 이분탐색을 통해 정답을 찾아 나가야 합니다. 효율적인 정리를 위해 연약한 로봇은 각자가 처리할 수 있는 장난감들이 있다면 그 중에서도 가장 크기가 큰 장난감들부터 정리해나가면 됩니다. 연약한 로봇의 처리가 끝난 후 작은 로봇들은 정리가 되지 않은 장난감들을 처리해나가는데, 크기가 가장..

문제 www.acmicpc.net/problem/15590 알고리즘 greedy 풀이 $N$마리의 소, $M$명의 우유 구매자, $R$명의 대여 희망자가 주어질 때, 얻을 수 있는 최대 수익을 구하는 문제입니다. 소를 우유 생산량에 따라 정렬해놨을 때, $i$번 소까지는 대여를 하고, 그 이후의 소들은 젖을 짜 우유를 판매하는 것이 최적이므로 우리는 어느 소까지만 대여를 해줄지 구해야합니다. 일단 모든 소를 대여해준 후 가장 가치가 높은 소(우유 생산량이 가장 많은 소)부터 우유를 짜서 가장 비싸게 사는 사람에게 판매합니다. 대여 희망자에 대한 누적합을 구해놓았다면 $i$번째 사람까지 대여를 했을 때 벌 수 있는 돈을 $O(1)$에 구할 수 있습니다. 이때 정답이 더 크게 갱신이 된다면 계속 진행을 하고..

문제 www.acmicpc.net/problem/17024 알고리즘 Greedy 풀이 인접한 지역과 거의 인접한 지역에 다른 종류의 풀을 심어야 할 때, 풀 종류의 최솟값을 묻는 문제입니다. 주어진 예제말고도 그림을 그려 특징을 파악하며 풀면 됩니다. 한 노드 A에 인접한 노드 B, C, D가 있다고 가정해봅시다. 이 노드들은 A와는 무조건 다른 종류의 풀을 사용해야만 합니다. 하지만 A를 제외한 B의 인접 노드에 풀을 심을 때는 A와 다른 종류의 풀을 심어야 하지만(A는 두칸이 떨어져 있어 거의 인접한 지역이므로) C, D에 심었던 풀을 심을 수 있음을 관찰하면 됩니다. 일반화하면 노드 중 최대 indegree값 + 1 이 정답입니다. 코드 #include #define rep(i, n) for (in..

문제 www.acmicpc.net/problem/1744 알고리즘 Greedy 풀이 수들이 주어졌을 때, 각 수들을 적절히 묶어 모든 수들의 합이 최대가 되도록 하는 문제입니다. 직관적인 그리디한 문제입니다. 두 수의 묶었을 때 가장 크기 위해서는 각 수가 첫번째로 큰 수, 두번째로 큰 수가 되어야합니다. 단 놓치기 쉬운 포인트 중 두 수를 묶는 조건입니다. 두 수가 음수면 무조건 양수로 만들 수 있으니 곱해나가는 것이 맞으나 두 수가 양수여도 두 수의 곱보다 합이 작을 경우 묶어서는 안됩니다. 예를 들어 수가 1, 1이라면 곱하는 것 대신 두 수를 더하는 것이 더 이득이기 때문입니다. 아래 코드는 양수와 음수를 구분하여 벡터에 넣은 후, 음수벡터의 크기가 홀수라면 1을 추가합니다. 양수 벡터는 수를 따..