DP3 leetcode 1510 - Stone Game IV https://leetcode.com/problems/stone-game-iv/ 풀이 Alice가 선택할 수 있는 모든 경우를 다 해봐서 이길 수 있는 경우가 하나라도 있으면 그 길을 선택하면 된다. 최소 한 개 이상을 가져가기 때문에 stone이 1개 있는 경우부터 차례대로 n까지 구해간다면 점화식을 세울 수 있다. 매 턴이 바뀔 때마다 Alice, Bob 유저가 바뀌므로 d 배열을 정의할 때 선공하는 사람이 최선을 다할 때 이길 수 있는지 여부를 저장해야 한다. d[i] = i개의 stone이 있을 때 선공하는 사람이 이길 수 있으면 true, 무조건 지면 false 이 전 상태를 참조할 때 턴이 바뀌기 때문에 d 배열에 false가 하나라도 있으면 그 길을 선택하는 것이 최선이다. 코드 class .. 2020. 11. 25. leetcode 1406 - Stone Game III https://leetcode.com/problems/stone-game-iii/ 풀이 모두가 최선을 다하기 때문에 현재 상태에서 한 개 가져갔을 때, 두 개 가져갔을 때, 세 개 가져갔을 때를 비교해서 가장 좋은 선택을 할 것이다. 세 가지 경우를 재귀적으로 반복해서 마지막까지 진행한다. 이렇게 모든 stone을 가져가서 빈 배열까지 오면 승패를 알 수 있으므로 재귀의 기저 조건으로 둘 수 있다. 이를 활용해서 d 배열을 아래와 같이 정의하고 점화식을 세우면 된다. d[i] = stoneValue의 [i, n) 부분에서 선공했을 때 얻는 최대 이득 이렇게 정의한 후 뒤에서부터 0번째까지 d값을 구하면 현재 stoneValue에서 누가 이기는지 한 번에 알 수 있다. 코드 class Solution { .. 2020. 11. 24. leetcode 877 - Stone Game https://leetcode.com/problems/stone-game/ 풀이 현재 플레이어가 할 수 있는 액션은 왼쪽 pile을 가져가거나 오른쪽 pile을 가져가거나 둘 중 하나다. 따라서 두 가지 경우 중 더 유리한 경우를 선택하면 된다. 재귀적으로 하나씩 계속 가져갔을 때 가장 마지막 상태, 즉 pile이 한 개 남은 상태라면 승패는 명확하다. 선공을 통해 먼저 가져가면 이긴다. 그러면 이제 반대로 맨 마지막 기저 조건과 점화식을 통해 식을 세울 수 있다. 점화식을 세울 때 단순히 이기고 지는 정보만 저장하면 안 되고, 서로 최선을 다했을 때 얼마나 차이가 나는지 까지 저장을 해야 한다. d[i][j] = i부터 j까지 pile로 게임을 진행할 때 선공을 한 사람이 가져갈 수 있는 최대 이득 아.. 2020. 11. 22. 이전 1 다음
