[수업]Card Game

Intro..

이 문제는 NIM게임 관련 문제이다.

결국 DP같은 형태로 풀게 될 것이다.

DP, NIM 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

문제의 의미는 양끝에서만 카드를 집어갈 수 있는 조건이며, 마지막에 총합해서 젤 높은 숫자를 뽑은 사람이 승자 게임.

2차원 배열 => 재귀 + DP형태로 풀었음(top-bottom)

교수님 풀이는 bottom-top 방식!! => 추천

left, right로 양쪽 끝을 index..

앨리스가 먼저 시작하게끔 알고리즘 구성

=> left+1과 right-1 양쪽 끝 접근형태로 앨리스 먼저 시작하게 코드.

COMPUTER는 단순히 양쪽끝에서 MAX값을 가져가게끔.(먼저시작하거나 하질 않으니 이것만 생각)

앨리스는 먼저 시작이니 left or right 값을 먼저 + 해주고, COMPUTER가 기록한 값들중 MIN값을 더해줘야 앨리스가 더 숫자 높은 상태가 됨.(COM이 MIN이야 앨리스가 당근 더 높으니까)

중복 계산 차단은 COMPUTER때 if!=0으로!(dp배열 사용)

2차원 배열이 아래 형태로 그려져가며, 대각선으로 채워져 나감.(따라서 위의 규칙만 잘 지키면 bottom-up 방식으로 더 간단히 풀 수도 있을것임. 예로 앨리스면 하위 양끝중 MIN값택, 컴퓨터면 하위 양끝중 MAX값택 형태로 채워나가면 될것임)

=> 파란선을 따라가보면 대각선먼저 쌓여가는 재귀 형태란점을 볼 수 있음

=> 4x4로 손으로 풀어본 것

교수님 풀이 - card game

데이터 : 2 5 100 3 7 6 => 데이터 : x x x i … j x x x

2차원배열 curr, next 2개 이용해서 대각선방향으로 구해감

dp배열을 curr(i,j) 라 하면, curr(1,n)을 구하는게 목표(1…n사이 최대합을 의미)

• curr(i,j)는?
  • i…j사이 최대합을 의미
• dp배열을 하나더 사용 - next(i+1,j)
  • 다음 차례(상대방)의 i+1…j사이 최대합 의미
• Sum(i)는 i까지의 누적합( 이것도 필요함 )
• card(i)는 i번째 카드 값

• i는 행, j는 열이겠지만. i,2,3,4,…j(n) 이런식으로 card 순번으로도 유동적으로 생각해줄것

1,2번째 for문은 당연한 기본 초기값 세팅

• curr[i][i]는 i..i니까 card[i]번째 값인게 자명
• next[i][i]는 curr이 이미 i..i를 가져갔으므로 0인게 자명

if (j-i)==1, curr(i,j) = max(card(i), card(j))

• j-i==1이면 i와 j차이가 1이니까 i다음 j인것.

• 그럼 당연히 i번 카드와 j번 카드중 큰값을 curr에 반영해야 이김

• 이방식을 활용하자는것!! 아래식 도출 가능

curr(i,j)=max(card(i)+next(i+1,j), card(j)+next(i,j-1))

• 그다음 next구하는것은?? 아래식!

Sum(j)-sum(i-1)-curr(i,j)

• Sum(j)-sum(i-1)는 i…j까지 누적합을 의미.
• 여기서 현재 i…j구한 최대합 curr(i,j)를 빼주면 다음 차례의 next(i,j)가 도출