[Leetcode] 452. Minimum Number of Arrows to Burst Balloons
문제 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/ points 배열을 start 기준 오름차순, start가 동일한 경우 end 기준으로 오름차순 정렬한다. points 배열을 앞에서부터 탐색하면서 중복되는 범위를 저장해둔다. (let, duplicate) duplicate 범위의 start가 end 보다 작아지는 경우 정답을 +1 하고 현재 탐색중인 points 배열 원소값으로 duplicate를 갱신한다. 문제의 예제 1번 예시. points = [[10,16],[2,8],[1,6],[7,12]] [1, 6] x -> [1, 6] 갱신 (정답 + 1) [2, 8] [2, 6] [7, 12] [7, 6] -> [..
2022. 1. 13.
[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.