Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/10835
10835번: 카드게임
첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오
www.acmicpc.net
풀이
간단한 DP문제였지만 bottom-up 방식으로만 접근하다 top-down 방식으로 해보니 쉽게 풀렸다.
bottom-up 방식을 연습하는 것은 좋지만 문제마다 top-down 방식이 익숙하다면 먼저 재귀로 푼 후에 변환해보자.
단순히 생각하면 왼쪽 카드에서 가장 큰 수가 나올때 까지 모두 버려버리고 오른쪽 카드의 점수를 획득하는 그리디 방식을 떠올릴 수 도 있다.
하지만 왼쪽 카드의 최댓값 보다 큰 오른쪽 카드가 있다면 2번의 경우처럼 같이 버려줘야 아래 카드의 점수들도 모두 얻을 수 있다.
각 카드의 순서에서 가능한 최대값을 저장하는 DP방식으로 해결한다.
해당 문제에서 플레이는 3가지로 분기한다.
1. 왼쪽카드(l)만 버린다. (언제든지 가능)
2. 왼쪽카드와 오른쪽 카드(r)를 같이 버린다. (언제든지 가능)
3. 오른쪽 카드를 버리고 점수를 얻는다. (왼쪽 카드가 더 큰 경우에만)
3번의 경우만 조건과 획득 점수가 있기 때문에 왼쪽 카드가 더 큰 경우에만
right_card[r] + playCardGame(l,r+1)를 진행하고
1번은
playCardGame(l+1, r)
2번은
playCardGame(l+1, r+1)
각각 호출하여 3가지 경우 중 최댓값을 cache[l][r]에 저장하여 반복 연산을 방지한다.
코드
bottom-up 방식
우리는 (l,r)에서의 최댓값을 얻기위해 (l+1,r), (l,r+1), (l+1,r+1)의 값을 사용했다.
따라서 카드를 모두 소진한 마지막 행,열에는 0을 채워준후 역순으로 값을 계산해 주면된다.
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.2629 - 양팔저울 (C++) (0) | 2020.12.02 |
|---|---|
| [백준] No.12865 - 평범한 배낭 (C++, 배낭 문제) (0) | 2020.12.01 |
| [백준] No.2491 - 수열 (C++) (0) | 2020.11.29 |
| [백준] No.1495 - 기타리스트 (C++) (0) | 2020.11.28 |
| [백준] No.10164 - 격자상의 경로 (C++) (0) | 2020.11.27 |