전체 글61 DP - 도둑질 프로그래머스 (DP) - 도둑질 해당 문제는 원형의 집 배치라는 것을 생각하고, 첫번째 집을 선택하고, 마지막집을 선택하지 않은 경우, 첫번째 집을 선택하지 않은 경우로 나누어, dp[n] = Max(dp[n-2] + money[n], dp[n-1]) 이라는 기준으로 계산(2번째 전집을 털고, 현재 집을 털 경우와 이 전집을 턴경우) 식을 바탕으로 2가지 경우를 구한 후 두가지중 큰 값을 선택하여 값을 구했습니다. public int solution(int[] money) { int homeLength = money.length; int[] dpFirstChoice = new int[homeLength]; int[] dpFirstNotChoice = new int[homeLength]; dpFirstCh.. 2022. 3. 9. DP - 등굣길 프로그래머스(DP) - 등굣길 해당문제는 해당 좌표로 올 수 있는 경우의 수 dp(x,y) = dp(x-1, y) + dp(x, y-1)로 나타 낼 수 있습니다. 이 중 제한 사항인 물이 잠긴 지역으로 갈 수 있는 방법은 0이라 생각하고 계산을 하는 방식으로 진행했습니다. 입력 받은 2차원 배열 puddles에서 해당 puddle 좌표를 구해 물이 잠긴 지역을 표시하고 계산을 진행 하는 중에 물이 잠긴 지역인 경우 계산 없이 0으로 값을 셋팅했습니다. 계산 후 1,000,000,007을 한 이유는 문제 결과로 해당 숫자로 나눈 나머지를 return 하라고 했었고, 계산값이 int의 max value를 넘는 경우도 있을 것으로 보이기에 그렇게 구현하였습니다.(프로그래머스에서 마지막 dp[m][n] 만 DI.. 2022. 3. 8. DP - 정수 삼각형 프로그래머스 (DP) - 정수 삼각형 해당 문제는 이전 층의 좌,우 dp의 합 중 큰 값과 더하는 문제였습니다. dp(x, y) = triangle(x,y) + MAX(dp(x-1, y좌), dp(x-1, y우)) 라는 것으로 마지막층까지 총 합을 저장한 dbTriangle 이중배열을 만든후 마지막 층의 dp 합 중 가장 큰 값을 return해주었습니다. public int solution(int[][] triangle) { int height = triangle.length; int[][] dpTriangle = new int[height][]; dpTriangle[0] = new int[]{triangle[0][0]}; for (int i = 1; i < triangle.length; i++) { d.. 2022. 3. 7. 이전 1 ··· 10 11 12 13 14 15 16 ··· 21 다음