HARD56 [Leetcode][124] Binary Tree Maximum Path Sum 문제 : https://leetcode.com/problems/binary-tree-maximum-path-sum/ 서브트리의 루트 노드를 기준으로 만들 수 있는 sequence들은 다음과 같다.1. 현재 루트노드, 루트노드의 왼쪽, 오른쪽 노드를 sequence로 가지는 경우. 2. 왼쪽 노드와 부모노드를 sequence로 가지는 경우왼쪽 자식노드 value가 오른쪽 자식노드보다 크고 root와의 합이 0이거나 양수인 경우이다. 3. 오른쪽 노드와 부모 노드를 sequence로 가지는 경우오른쪽 자식 노드가 왼쪽 자식노드보다 크고 오른쪽 자식 노드와 root노드의 value를 합한 값이 양수인 경우이다. 4. root노드만을 sequence에 포함시키는 경우이 경우는 왼쪽 자식 노드와 오른쪽 자식 노드.. 2018. 12. 10. [leetcode][920] Number of Music Playlists 문제 : https://leetcode.com/problems/number-of-music-playlists/ DP로 풀었다.dp[N][L] = N개의 노래로 L개의 노래가 있는 플레이 리스트를 만드는 경우의 수. 만약 i개의 노래로 j개의 노래가 있는 플레이 리스트를 만들었다고 할 때(dp[i][j]) 다음에 추가하는 노래는 플레이리스트에 없는 노래거나 플레이리스트에 이미 있는 노래. 이렇게 2가지 경우가 있다. 플레이리스트에 없는 노래를 추가한다면 만들어지는 dp배열은 dp[i+1][j+1]이다. (노래가 하나 추가되고 플레이리스트도 하나 느므로)dp[i][j]가 추가될 수 있는 노래의 개수(N - i = 전체 - 이미 들은 노래)만큼 추가되므로 dp[i+1][j+1] += dp[i][j] * (N .. 2018. 11. 6. 이전 1 ··· 7 8 9 10 다음
