DP
-
[백준 11062 - JAVA] 카드 게임Algorithm 2020. 11. 12. 18:32
11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 정말정말 DP는 풀 때마다 모르겠다! 결국 블로그를 참고해서 어떻게 푸는지 보고 풀었다. 최선의 전략으로 진행하는 것이기 때문에 모든 경우를 확인해야하고, DP를 이용해 각 턴마다 근우가 높은 점수를 얻는 경우와 명우가 낮은 점수를 얻는 경우를 저장해둔다. 그래서 DP배열은 [근우와 명우의 턴][시작 카드(왼쪽 끝)의 인덱스][마지막 카드(오른쪽 끝)의 인덱스]로 크기는 [2][N][N]으로 할당한다! 풀이 방법 DP배열의 초기값을 -1로 넣어준다. 턴은 근우부터 0..
-
[백준 1937 - JAVA] 욕심쟁이판다Algorithm 2020. 11. 9. 19:28
1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 현재 장소보다 대나무가 많은 지역으로만 이동할 수 있는 판다가 가장 오래 살아남는 기간을 구하는 문제! 단순하게 dfs로 풀었다가 시간초과를 받았다. DP라고해서 고민을 하다가 결국 블로그를 참조했다. 기간을 정해서 DP문제를 집중적으로 푸는 시간을 가져야 할 것 같다... ŏ̥̥̥̥םŏ̥̥̥̥ 풀이 방법 dfs를 통해 끝에 도달했을 때 그곳의 cnt(살아남은 날짜)는 1이 된다. * 더 이상 이동하지 못하기 때문에 그곳에서는 하루만 살 수 있다. 그리..