[leetcode] 354. Russian Doll Envelopes
문제 : https://leetcode.com/problems/russian-doll-envelopes/ 배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다. 정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다. 결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다. 위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다. [[4,5],[4,6],[6,7],[2,3],[1,1]] 입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다. height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려..
2022. 5. 26.
[leetcode] 1463. Cherry Pickup II
문제 : https://leetcode.com/problems/cherry-pickup-ii/ rows x cols 체리 필드(grid)가 주어지고 각 요소값은 체리 수를 의미한다. 로봇1은 왼쪽 상단 (0,0)에서 출발하고 로봇2는 오른쪽 상단 (0, cols-1)에서 출발한다. 셀 (i,j)에서 로봇은 (i+1, j-1), (i+1, j), (i+1, j+1) 3가지 중에 한 곳으로 이동할 수 있다. 두 로봇이 동일한 셀에 있을 때 한 로봇만 체리를 가져갈 수 있다. 로봇들이 이동할 때, 수집할 수 있는 체리의 최대 수를 구해라. DP로 풀 수 있다. dp[row][col1][col2] = 로봇1은 (row, col1), 로봇2는 (row, col1)에 있을 때 수집가능한 체리수의 최대값. dp[ro..
2022. 1. 11.