My Tech Blog (DP)

📑 1. 문제설명💡 2. 접근방식 풀이방법1. dp[][] 배열 선언 2. 첫 번째 줄 값 채우기 (dp[0][0] = triangle[0][0])2. 왼쪽 첫번째 열인 dp[i][0] 값은 이전 줄의 첫 번째 값끼리 더해서 입력한다. (dp[i][0] = dp[i-1][0] + triangle[i][0]) 3. 그 외의 값들은 위쪽과 왼쪽에서 오는 값을 비교하여 최대값을 더하기(dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]) 즉, 위쪽에서 오거나 왼쪽 위에서 온 값 중 더 큰 값에 현재 triangle[i][j] 값을 더한다. dp[][] 배열 선언나처럼 수학을 어려워하는 사람들을 위해 배열을 눈으로 보기 쉽게 시각화 해 보았다.코..

📑 1. 문제설명계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다.  가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항격자의 크기 m, n은 1 이상 ..