기록공간

그리디 알고리즘 문제이다. 끊어진 (적어도)N개의 기타줄을 사기위한 최소 비용을 구하기 위해서는 우선 브랜드 별로 오름차순으로 정렬하여 가장 싼 패키지 가격과 가장 싼 낱개 가격을 각각 구해준다. N이 6이상일 경우 패키지 가격으로 살 것인지 아니면 낱개 가격을 살것인지를 먼저 정해야 한다. 전자의 경우 N을 6과 나누어 나온 값 만큼 패키지 가격을 곱하여 최종 가격에 더해준다. 그리고 만약에 나머지 사야할 기타줄이 있는 경우, 그 갯수와 낱개의 곱이 패키지의 가격을 넘는다면 패키지 가격을 최종 가격에 더해주고 아닌경우 (낱개가격 * 사야할 기타줄 수)를 더해준다. 후자의 경우에는 그냥 (낱개가격 * 사야할 기타줄 수)를 더해주면 된다. 코드는 다음과 같다. #include #include using n..

그리디 알고리즘 문제이다. 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 예를 들어 A의 지원자가 B 지원자보다 서류 심사나 면접시험 중 하나라도 더 높다면 선발이 되고, 둘 다 낮다면 절대 선발되지 않는다. 알고리즘은 다음과 같다. 우선 서류 전형 순위를 오름차순으로 정렬한다. 정렬 후 가장 첫번째에 있는 사원은 조건에 무조건 만족하므로 선발한다. 선발된 사원의 면접 순위를 N에 기록하고 다른 지원자들의 면접 점수를 검사한다. 만약 지원자의 면접 순위가 N보다 작은 경우 조건에 만족하므로 선발하고 순위를 다시 N에 기록한다. 코드는 다음과 같다. #include #include using namespace std; struct ..