DP3 [DP] 2578번 계단 오르기 https://www.acmicpc.net/problem/2578 알고리즘 Dynamic Programming 풀이 포인트 bottom-up 구현 세 계단을 연속적으로 오르지 못하는 제한 조건을 활용하여 점화식 변형 Dynamic Programming 전형적인 dp 문제로, i번째 계단을 방문했을 때, 그 상태를 기반으로 i+1번째 계단, i+2번재 계단을 방문할 때의 점수 상태를 업데이트하면 된다. 이때, 연속적으로 3개의 계단을 방문하면 안되므로, i번째 계단 방문 상태가 이미 연속 두 계단을 방문한 상태라면 i+1번째 계단은 방문 못하고 i+2번째 계단만 방문할 수 있다. 만약, 연속 두 계단이 아닌, 연속 하나의 계단만 방문한 상태라면 i+1,i+2 계단 모두 방문할 수 있다. 우선 2차원 dp .. 2022. 1. 29. [DP] 15990번 1,2,3 더하기 5 https://www.acmicpc.net/problem/15990 알고리즘 Dynamic Programming 풀이 포인트 같은 숫자를 여러번 사용할 수 있지만 연속적으로 사용할 수 없다는 점 Dynamic Programming 같은 숫자를 연속적으로 사용할 수 없다는 점에 착안하여, DP 테이블을 2차원으로 정의한다. $dp[i][j]$: 맨 마지막 수가 $j$면서 정수 $i$를 만들 수 있는 경우의 수 $1+2+2$: $dp[5][2]$에 포함되는 경우의 수임 점화식 $j == 1$이면, $dp[i][j] = dp[i-j][2] + dp[i-j][3]$ $j == 2$이면, $dp[i][j] = dp[i-j][1] + dp[i-j][3]$ $j == 3$이면, $dp[i][j] = dp[i-j][1.. 2022. 1. 9. [DP] 9095, 15988번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 https://www.acmicpc.net/problem/15988 알고리즘 Brute Force Dynamic Programming 풀이 포인트 같은 숫자를 여러번, 연속적으로 사용해도 된다는 점 정수 n을 구성하는 숫자의 순서는 상관 없다는 점 1+1+2, 1+2+1, 2+1+1은 모두 다른 경우의 수 정수 n을 구성하는 숫자의 개수의 제한이 없다는 점 Brute Force 문제에서 n은 11보다 작다. 따라서 n은 최대 10개의 수로 구성될 수 있다. 그러면 각 자리마다 가능한 정수 (1,2,3)를 모두 놓아봄으로써 가능한 경우 (그 정수들의 합이 n)만 체크해주면 된다. Brute Force로 프로그래밍할 때, 재귀를 이용하는 것을.. 2022. 1. 9. 이전 1 다음
