정리60 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. DP - N으로 표현 프로그래머스 (DP) - N으로 표현 해당 문제는 1번재와 2번째의 표현 가능 한 경우를 구한 후 3번째 부터는 첫번째와 2번째 가능수들의 사칙연산 조합 4번째는 1번째와 3번째, 2번째와 2번째의 가능 수들의 사칙연산 조합을 가지도록 로직을 구현했습니다. 순차적으로 모든 경우의 수를 계산하면서 number를 찾게되면 해당 번째를 return 하고 8번째를 넘게되면 -1을 return하도록 로직을 구현했습니다. 4번째를 구할때 3번째와 1번째의 조합은 1번째와 3번째의 조합과 같으므로 그 부분을 조합하는것은 예외로 처리했습니다. public int solution(int N, int number) { if (N == number) { return 1; } List expressList = new Arra.. 2022. 3. 4. 이전 1 ··· 7 8 9 10 11 12 13 ··· 15 다음