dotorya   4년 전

원문: http://topcoder.bgcoder.com/pr...

위 문제와 같은 문제인데, 약간 오해의 소지가 있을 것 같습니다.
저는 처음에 만들어진 두 그룹 이후에는 더 이상 그룹이 나누어지지 않는다고 생각했는데, 그 이후에도 계속해서 그룹이 나누어지네요.
그룹이 2개가 생긴다는 것도, 반드시 2개의 그룹이 생기도록 기타를 골라야 한다고 생각할 여지가 있는 것 같습니다.

따라서, 대략 아래와 같이 Description을 수정하면 어떨까 합니다.

---------------------

세준이는 상대방과 자유로운 기타 연주 대결을 벌이는 TV 쇼에 나갔다.

게임이 시작하기 전에 N개의 기타 케이스가 원형으로 놓여져 있다. (1 <= i < N에 대해 i번째 기타 케이스와 i+1번째 기타 케이스는 서로 인접해 있고, N번째와 1번째 기타 케이스도 인접해 있다.) 각각의 케이스 안에는 기타가 들어있다.

세준이와 상대방은 번갈아가며 기타를 가져간다. 두 사람은 각자의 차례에 모든 그룹에서 기타를 하나씩 골라서 꺼내 가져간다. 그룹이란 비어있지 않은 연속한 기타의 집합이다. 기타를 꺼낼 때마다, 그룹이 새로 생길 수도, 사라질 수도 있다.

이해를 돕기 위해, 다음과 같은 게임 진행을 생각해 보자. 

0. N = 8, 게임 시작 전 -> 현재 남은 그룹 : (1,2,3,4,5,6,7,8)

1. 세준이가 2번 기타를 가져감 -> 현재 남은 그룹 : (1,3,4,5,6,7,8)

2. 상대방이 7번 기타를 가져감 -> 현재 남은 그룹 : (1,8) (3,4,5,6)

3. 세준이가 1, 4번 기타를 가져감 -> 현재 남은 그룹 : (8) (3) (5,6)

4. 상대방이 3, 5, 8번 기타를 가져감 -> 현재 그룹 : (6)

5. 세준이가 6번 기타를 가져감 -> 현재 그룹 : 

6. 남은 기타가 없으므로 게임이 종료됨

세준이와 상대방은 고른 기타를 모두 버리지 않고 소중하게 놔두고 있다. 세준이는 세준이가 고른 기타의 가치의 합을 최대로 만들고 싶어한다. 기타의 개수와 가치가 주어졌을 때, 세준이가 고른 기타들의 가치의 합을 최대로 만드는 프로그램을 작성하시오. 게임은 항상 세준이가 먼저 시작하며, 두 사람은 최적의 전략을 구사한다고 가정한다.

-----------------
확인 후 수정해주시면 감사하겠습니다!

baekjoon   4년 전

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.