작성자 | Zergterratoss | ||
---|---|---|---|
작성일 | 2011-06-12 14:34:30 KST | 조회 | 208 |
제목 |
이거 힌트좀 주실분
|
문제 꽃진열
경빈이는 꽃가게를 경영한다. 하지만 각각의 꽃에는 어울리는 꽃병이 있는법, 손님에게 더욱 이쁘게보이기 위해서는 꽃장식을 아름답게 하여야한다. 경빈이는 꽃장식을 혼자서 끝내려 했으나, 그게 가장 이쁘게 꾸민 것인지 확신이 서지 않았다. 그래서 경빈이는 IM4U친구들에게 도움을 청했다.
경빈이의 꽃가게에는 F개의 서로 다른 꽃이 있고, 꽃의 개수 이상인 꽃병들이 한 줄로 서 있다. 꽃병들은 선반에 붙어 있으며, 왼쪽부터 오른쪽으로 1, 2, ..., V까지 차례대로 번호가 매겨져 있다. 꽃은 아무 꽃병에나 꽂을 수 있으며 역시 1, 2, ..., F로 번호가 붙어 있다. 꽃병이 꽃보다 개수가 더 많으면 남는 꽃병은 비게 되며, 하나의 꽃병에는 하나의 꽃만 꽂을 수 있다. 그리고 중요한 규칙이 있는데, 번호가 작은 꽃은 반드시 번호가 더 큰 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 왼쪽부터 오른쪽으로 훑을 때 꽃병의 번호는 물론 꽃의 번호까지 오름차순을 유지해야 한다는 말이다.
앞에서 말했듯이 꽃을 어떤 꽃병에다 꽂느냐에 따라 다른 미적 가치가 정수 값만큼 생긴다. 이 정보는 아래의 표처럼 제시된다. 단, 빈 꽃병의 미적 가치는 0이다.
꽃병 꽃 | 1 | 2 | 3 | 4 | 5 |
1 진달래 | 7 | 23 | -5 | -24 | 16 |
2 베고니아 | 5 | 21 | -4 | 10 | 23 |
3 카네이션 | -21 | 5 | -4 | -20 | 20 |
위의 표에 따르면 진달래는 2번 꽃병에 꽂으면 매우 아름답게 보이지만 4번 꽃병에 꽂으면 상당히 보기 싫어지게 된다.
창가 조경을 가장 아름답게 하려면 위에서 제시한 규칙을 지키면서 꽃들이 만들어낸 미적 가치의 합이 최대가 되어야 한다. 이럴 경우에는 1번 꽃을 2번 꽃병, 2번 꽃을 4번 꽃병, 3번 꽃을 5번 꽃병에 꽂으면 23+10+20이 되어 가장 아름다운 장면이 펼쳐진다. 최대값이 나오는 경우가 여러 가지가 있다 해도 그 중 한 가지만 출력하면 된다.
손님을 끌기위해 도움을 청한 경빈이를 위해 꽃을 아름답게 장식하자.
<제한>
1 <= 꽃의 수 <= 꽃병의 수 <= 100
-50 <= 미적 가치 <= 50
프로그램의 실행 제한 시간은 1초이다. 부분 점수는 없다.
첫 줄에는 꽃의 수 F와 꽃병의 수 V가 들어있다. 다음 F개의 줄에는 각각 V개의 정수가 있다. (i+1)번째 줄의 j번째 수가 i번 꽃을 j번 꽃병에 넣었을 때의 미적 가치가 된다.
첫 줄에는 최대 점수를 출력한다. 둘째 줄에는 F개의 정수를 출력한다. k번째 정수는 k번째 꽃이 꽃힐 병의 번호이다.
입력의 예(INPUT.TXT) 출력의 예(OUTPUT.TXT)
3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 |
53 2 4 5 |
|
||
|
|
||
|
|
||
|
© PlayXP Inc. All Rights Reserved.