Algorithm/다이나믹 프로그래밍(DP)

[백준, Java] 5557번 : 1학년

🔗 문제 링크 https://www.acmicpc.net/problem/5557 😮 문제 해결 방법 처음부터 숫자를 더하거나 빼면서 그 값이 0이상 20이하가 되어야 한다. 완전탐색으로 문제를 풀기에는 경우의 수가 무수히 많기 때문에 DP를 이용한다. dp 배열의 사이즈는 마지막 숫자를 제외한 숫자의 개수, 0 - 20까지 경우의 수를 저장하게 dp[N-1][21]로 지정한다. 마지막 숫자는 수식의 = 이되기 때문에 마지막 숫자는 배열에서 제외한다. 배열에는 매 인덱스 별 계산한 결과값의 경우의 수가 저장되어있다. 따라서, N-1 인덱스까지 숫자의 인덱스를 옮겨가면서 이전 인덱스까지 결과값 0에서 20까지의 경우의 수 중 1번 이상 결과가 나온 값을 더하거나 빼준다. 더하거나 빼준 값이 다시 0이상 20..

[프로그래머스, Java] 땅따먹기

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12913 😮 문제 해결 방법 간단한 DP문제이다. 현재 스텝의 열에서 최대의 점수를 얻기 위해선 이전 스텝까지의 열 중에서 현재 내가 밟고 있지 않은 열의 최대 점수값을 더해준다. 만약 2번째 스텝의 1번째 열의 최대값을 구하고 싶다면, 1번째 스텝까지의 2,3,4열의 최대값에 현재 밟은 칸의 점수를 더해주면 최댓값이 된다. 이러한 방식을 통해 점화식을 세우면 dp[step][열] = arr[step][열] + max(dp[step-1][열에 해당하지 않는 열])이 된다. dp[step-1][열에 해당하지 않는 열]의 경우 열이 4개가 있기 때문에 max안에 들어가는 dp의 개수는 3개..

[백준, Java] 9465번 : 스티커

🔗 문제 링크 https://www.acmicpc.net/problem/9465 😮 문제 해결 방법 매 열마다 1행 혹은 2행의 스티커를 뜯었을 때의 최대 점수를 구해주면 되기 때문에 2차원 배열로 선언해준다. 최대 점수는 n열까지 모두 뜯었을 때 1행 n열 혹은 2행 n열의 점수 중 큰 점수가 가장 최대로 구할 수 있는 점수이다. 현재 열이 3열이라고 가정하고 스티커를 뜯는 경우를 판단해보자. 3열의 스티커를 뜯는 경우는 1행 3열, 2행 3열의 스티커를 뜯는 경우 2가지이다. 1행 3열의 스티커를 뜯는 경우 → row : 0 col : 2 인접한 변을 가진 스티커는 뜯을 수 없기 때문에 **이전 열 대각선(현재 행과 반대되는 행)**에 위치한 최대 점수 값과 현재 스티커 점수를 더해준다. → dp[p..