분류 전체보기105 [DP] 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 알고리즘 Dynamic Programming 풀이 포인트 계단 수는 각 자리 수와 바로 옆의 수가 1만큼만 차이가 나는 수를 의미한다. Dynamic Programming DP로 해결할 수 있는 문제의 특징은 $n$까지의 상황이 $n+1$의 상황에 영향을 미친다는 것이다. 이러한 점화식이 성립이 되면 $n+1$의 상황을 생각할 때 그 이전의 상황, 즉 $n,n-1$번째의 상황을 심각하게 고려할 필요가 없다. 이 문제도 비슷하게 풀 수 있다. $n$자리의 계단 수의 개수를 구했다고 생각해보자. $n+1$자리의 계단수의 개수를 구하기 위해서는 $n$번째 자리만 고려하면 된다. 계단수가 되기 위한 조건이, 바로 옆 자리수와 1만큼만 차이가 나.. 2022. 1. 9. [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 ··· 15 16 17 18 다음
