(글 몇번 안올려봐서그런데 문제되는거있으면 알려주세요.)

 

선생님께서도 점화식은 맞는 것 같다고 하시던데 2시간 동안 찾았는데도 못고치겠더라고요.

문제는

 

/

두 플레이어가 있다.

N개의 양의 정수의 원형으로 배열한다.

① 첫 번째 플레이어는 임의의 수를 선택할 수 있다.
② 두 번째 플레이어는 첫 번째 플레이어가 선택한 수의 인접한 두 개의 수 중에서 어느 것이든 선택할 수 있다.
③ 다음 플레이어는 마찬가지 방법으로 이미 선택된 수들과 인접한 수들을 더 이상 선택할 수 있는 수가 없을 때까지 두 명의 플레이어가 번갈아가며 선택한다. 더 많은 홀수(2로 나눠떨어지지 않는 수)를 선택한 플레이어가 최종 게임에서 승리한다.

두 플레이어는 최선의 전략으로 게임에 임한다. 이때 처음 시작하는 플레이어가 이기기 위해 첫번째로 택할 수 있는 정수는 몇가지 인가?

/ 입니다.

 

입력은 N과 정수들이 들어오고 출력은 가짓수만 출력하면 됩니다.

배열을 2*N까지 채워넣은 이유는 정수들이 원형으로 배열되어있기 때문입니다.

a[i]는 정수들의 2로 나눈 나머지를 입력받는 배열입니다. 또한 a[i+n]에는 a[i]를 집어넣었습니다.

s[i]는 a[1]부터 a[i]까지의 합입니다.

 

/점화식 설명

d[x][y]는 x부터 y까지 위치에 있는 정수들에 대하여 첫번째 플레이어로 게임을 한다고 할때 얻을 수 있는 최적해입니다.

문제 구조상 선택된 정수들은(위치가) 모두 연속되어있습니다. 따라서 선택할 수 있는 정수는 양 끝 값입니다. 양 끝값의 위치는 x,y입니다.

d[x][y]는 처음에 a[x]또는 a[y]를 선택할 수 있습니다. a[x]를 선택한다고 할 때 두번째플레이어가 얻을 수 있는 최적해는 d[x+1][y]입니다.

첫번째 플레이어는 x+1부터 y까지 점수 총합 (s[y]-s[x]) 중 d[x+1][y]를 제외한만큼의 점수를 추가로 얻을 수 있습니다.

따라서

if(d[x][y]< a[x]+s[y]-s[x]-d[x+1][y])
    d[x][y] = a[x]+s[y] - s[x] - d[x + 1][y]; 입니다.

마찬가지로

if (d[x][y] < a[y]+s[y - 1] - s[x - 1] - d[x][y - 1])
    d[x][y] = a[y]+s[y - 1] - s[x - 1] - d[x][y - 1]; 입니다.

/

 

 

#include<stdio.h>
int d[201][201];
int n;
int cnt;                        / 출력값.
int s[201];
int a[201];

int main(void)
{
 scanf("%d", &n); 
 int i, j;
 int x, y;

 for (i = 1; i <= n; i++)
 {
  scanf("%d", &a[i]);
  a[i] = a[i] % 2;
  a[i + n] = a[i];
  s[i] = s[i - 1] + a[i];
 }
 for (i = 1; i <= n; i++)
  s[i + n] = s[n] + s[i];

 for (i = 0; i <= n-1; i++)
 {
  for (j = 1; j <= n; j++)
  {
   x = j;
   y = j + i;
   if(d[x][y]< a[x]+s[y]-s[x]-d[x+1][y])
    d[x][y] = a[x]+s[y] - s[x] - d[x + 1][y];
   if (d[x][y] < a[y]+s[y - 1] - s[x - 1] - d[x][y - 1])
    d[x][y] = a[y]+s[y - 1] - s[x - 1] - d[x][y - 1];
  }
 } 
 

 for (i = 1; i <= n; i++)
  printf("%d\n", d[i][i + n - 1]);
 int p1, p2;                                                 p1/ 첫번째 플레이어가  얻을수 있는 최적해, p2/ 두번째플레이어가 얻을 수 있는 최적해.
 for (i = 1; i <= n; i++)
 {
   p2= d[i + 1][n + i - 1];                                            
   p1 = s[n] - p2;
  if (p1 > p2)
   cnt++;
 }
 printf("%d", cnt);
 return 0;
}

 

문제가 되는 입력은

8
4 10 5 2 9 8 1 7

입니다 원래 출력은 5가 나와야 합니다.