leetcode17 leetcode 1563 - Stone Game V https://leetcode.com/problems/stone-game-v/ 풀이 Alice가 임의의 크기로 left와 right를 나눠서 더 작은 쪽의 점수를 얻으면, 그 뒤로 더 작은 쪽에서 같은 게임이 반복된다. 따라서 모든 크기로 나눠보고 재귀적으로 게임을 진행시킬 수 있다. 이 게임은 마지막 하나가 남을 때까지 진행되며 그 상태에서 Alice는 0점을 얻는다. 모든 subgame은 stoneValue의 subarray에서 이루어지기 때문에 중복된 연산을 방지하기 위해 아래와 같이 d 배열을 정의한다. d[i][j] = stoneValue의 [i, j] 부분에서 게임할 때 Alice가 얻는 최대 점수 매 subgame에서 가능한 경우를 탐색할 때 미리 구해놓은 sum 배열을 활용하면 좀 더 효율.. 2020. 11. 25. 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 1140 - Stone Game II https://leetcode.com/problems/stone-game-ii/ 풀이 처음에 M = 1 인 상태에서, 1 = n) return 0; if(d[index][m] != -1) return d[index][m]; int ans = 0; for(int i = index; i < min(n, index + 2*m); i++) { ans = max(ans, sum[index] - dfs(i+1, max(m, i-index+1))); } return d[index][m] = ans; } }; 2020. 11. 23. leetcode 877 - Stone Game https://leetcode.com/problems/stone-game/ 풀이 현재 플레이어가 할 수 있는 액션은 왼쪽 pile을 가져가거나 오른쪽 pile을 가져가거나 둘 중 하나다. 따라서 두 가지 경우 중 더 유리한 경우를 선택하면 된다. 재귀적으로 하나씩 계속 가져갔을 때 가장 마지막 상태, 즉 pile이 한 개 남은 상태라면 승패는 명확하다. 선공을 통해 먼저 가져가면 이긴다. 그러면 이제 반대로 맨 마지막 기저 조건과 점화식을 통해 식을 세울 수 있다. 점화식을 세울 때 단순히 이기고 지는 정보만 저장하면 안 되고, 서로 최선을 다했을 때 얼마나 차이가 나는지 까지 저장을 해야 한다. d[i][j] = i부터 j까지 pile로 게임을 진행할 때 선공을 한 사람이 가져갈 수 있는 최대 이득 아.. 2020. 11. 22. leetcode 1326 - Minimum Number of Taps to Open to Water a Garden https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/ 풀이 0부터 n까지 모든 점을 커버하는 최소한의 tab을 고르는 문제이다. 모든 점을 커버해야 하므로 0도 커버해야 하는데, 0을 커버하는 많은 tab 중에서는 가장 오른쪽 점까지 커버하는 tab을 고르는 것이 최선이다. 이렇게 고른 tab이 커버하는 가장 오른쪽 점을 r이라고 하자. 이다음 최선의 tab을 고르는 방법도 마찬가지이다. [0, r] 범위에 겹치는 범위를 가지는 다음 tab 중에 가장 오른쪽 점을 커버하는 tab을 고르면 된다. 그리디한 방법으로 tab을 고르는 게 항상 더 좋기 때문이다. 어차피 모든 점을 커버해야 하기 때문에 0부터 n 순서대로 .. 2020. 11. 22. 이전 1 2 3 다음
