https://programmers.co.kr/learn/courses/30/lessons/42896
코딩테스트 연습 - 카드 게임 | 프로그래머스
카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다. 1. 언제든지
programmers.co.kr
table[left_idx][right_idx] = left에서 idx만큼 빼내고, right에서 idx만큼 빼냈을 때의 최댓값
으로 점화식을 세운 것까지는 괜찮았는데,
조건에 맞게 table 값을 업데이트하는 코드를 작성하는 데 너무 오래 걸렸다.
index가 0부터 시작되다 보니, 초기값을 생성하는 데 꽤나 골치가 아팠어서.
결국 리스트 맨 앞에 초기값을 위해 insert(0, 0) 을 넣어서 해결했다.
1. 왼쪽 카드만 버릴 경우의 값, 왼쪽 오른쪽 둘 다 버릴 경우의 값 중 최댓값을 구한다
table[l_idx][r_idx] = max(table[l_idx-1][r_idx-1], table[l_idx-1][r_idx])
2. 이 값 중에서 오른쪽 카드만 버릴 수 있는 경우, 오른쪽 카드의 값을 더해준다.
if left[l_idx] > right[r_idx]: table[l_idx][r_idx] = max(table[l_idx][r_idx], table[l_idx][r_idx-1] + right[r_idx])
맨 마지막 값을 리턴하면 된다.
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 11403. 경로 찾기 (0) | 2020.02.24 |
|---|---|
| [Python] 백준 17406. 배열 돌리기 4 (0) | 2020.02.18 |
| [Python] 프로그래머스. 지형 이동 (Level 4) (0) | 2020.02.15 |
| [Python] 백준 13460. 구슬 탈출 2 (0) | 2020.02.14 |
| [Python] 백준 2110. 공유기 설치 (0) | 2020.02.13 |