반응형 정렬8 백준 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. 백준 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. 백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명 1. 용량이 적은 가방부터 채운다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 3. 남은 가방에 대해 1-2를 반복한다. 1. 용량이 작은 가방부터 채운다. 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의.. 2022. 1. 28. 이전 1 2 다음 반응형
