반응형 그리디16 백준 1083번 소트 - C++ 풀이 1. 그리디 하게 앞자리부터 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 3. S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수를 앞으로 끌어오기를 반복한다. 1. 그리디하게 앞자리부터 큰 수로 만들어야 한다. 결과가 사전 순으로 가장 뒷서도록 하려면 최대한 앞을 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져 있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 그리고 i번째 자리(A[i])에서 X칸 떨어져 있는 수(A[i+X])는 최소 X번의 스왑으로 i번째 자리로 끌어올 수 있다. A[i+X]를 A[i+X-1], A[i+X-2], ... 순으로 스왑하면 총 X번의 스왑으로 A[i+X]를 A[i]자리로 끌어오고, .. 2022. 6. 7. 백준 12169번 Infinite House of Pancakes - C++(cpp) 풀이 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다. 3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다. 1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다. 노말 턴과 스페셜 턴을 한 번씩 진행해야 한다고 하자. 노말 턴 → 스페셜 턴의 순서로 진행할 때보다, 스페셜 턴 → 노말 턴의 순서로 진행할 때 같거나 더 적은 시간이 든다. 현재 다이너가 d명 있다.. 2022. 3. 25. 백준 14789번 Oversized Pancake Flipper - C++(cpp) 풀이 1. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다. 3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다. 1. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 한 자리에서 두 번 이상 뒤집을 필요가 없다. 짝수번 뒤집는 것은 안 뒤집는 것과 같고, 홀수번 뒤집는 것은 한 번 뒤집는 것과 같기 때문이다. 따라서 각 자리에서 뒤집을지 말지만 결정하면 된다. 2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다. 뒤집을 수 있는 자리는 총 N-K+1개이다. 이때 첫 번째 팬케이크를 뒤집을 수 있는 자리는 가장 왼쪽의 K개를 뒤집는 자리뿐이다. 3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다.. 2022. 3. 23. 백준 1700번 멀티탭 스케줄링 - C++(cpp) 풀이 1. 이미 꽂혀있다면 스킵한다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 1. 이미 꽂혀있다면 스킵한다. 이미 꽂혀있다면 스킵해도 된다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 빈 자리가 있다면 빈 자리를 채우면 된다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 문제는 빈 자리가 없는 경우인데, 이때는 가장 나중에 사용할 것을 뽑는 것이 최적이다. 반대로 가장 나중에 사용할 용품이 아닌 것을 뽑았다고 치면, 그 전기용품 차례가 왔을 때 어차피 기존 것을 하나 뽑고 새로 꽂아야 하기 때문이다. #include #include #include using namespace std; const int MAX = 101; int N, K.. 2022. 3. 14. 백준 24508번 나도리팡 - C++(cpp) 풀이 1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다. 2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다. 3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있는 바구니에 모아야 한다. 1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다. 총 나도리의 수를 sum마리라고 하면, N개에 바구니에 흩어져있는 나도리들을 각 바구니에 K마리씩, 총 sum/K개의 바구니로 모으면 된다. 2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다. 남는 나도리 없이 전부 터트려야하므로 당연히 sum이 K의 배수가 아니면 무조건 불가능하다. 3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있.. 2022. 2. 23. 이전 1 2 3 4 다음 반응형
