Study hard

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ※점화식※ dp[i][j] : 길이가 i인 수의 i번째 자리에 j가 올 때 경우의 수 dp[1][1] ~ dp[1][9]까지 1로 초기화 해준다. if(j==9) dp[i][j] = dp[i-1][j-1] (마지막 수가 9면 그 앞 숫자는 8만 올 수 있다.) if(j==0) dp[i][j] = dp[i-1][j+1] (마지막 수가 0이면 그 앞 숫자는 1만 올 수 있다.) else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (0과 9 외의 수는 그 앞 숫자로 1 작거나 큰 수가 올 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net ※점화식※ dp[x] : x를 1,2,3의 합으로 나타내는 방법의 수 dp[1] = 1 (1) dp[2] = 2 (2, 1+1) dp[3] = 4 (1+1+1, 1+2, 2+1, 3) x번째 값은 x-3번째 값에 +3을 하거나, x-2번째 값에 +2를 하거나, x-1번째 값에 +1을 하므로, dp[x] = dp[x-3] + d..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2020/06/08 - [백준/DP] - 11726 2xn 타일링 기존 2xn 타일링에 경우의 수 하나 더 추가해주면 되는 문제. ※2x2타일로 시작하면 dp[x-2]만큼 경우의 수 있음 #include using namespace std; int n; int dp[1001]; void DP() { dp[1] = 1; dp[2] = 3; dp[3] = 5; for (int i = 4; i n; DP(); return 0; }

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp[i] : 2xi 크리 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 dp[1] : 1개 dp[2] : 2개 dp[3] : 3개 dp[4] 부터는 처음 타일이 2x1 한 개로 채워지는 경우와 1x2타일 두 개로 채워지는 경우로 나뉨 ※ 2x1 한 개로 채워지는 경우 남은 직사각형은 dp[x-1]의 경우의 수로 채워짐 ※ 1x2 두 개로 채워지는 경우 남은 직사각형은 dp[x-2]의 경우의 수로 채워짐 점화식 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 점화식 dp[i]:정수 i를 1로 만들기 위해 연산을 사용하는 최소 횟수 dp[x] = min(1+dp[x-1], 1+dp[x/2]) if(x%2==0) dp[x] = min(1+dp[x-1], 1+dp[x/3]) if(x%3==0) dp[x] = 1+dp[x-1] if(x%2!=0 && x%3!=0) #include #include //min using namespace std; int N; int dp[1000001];//최소 연산 사용 횟수 저장 void DP() { //초기값 설정 dp[1] = 0; d..

https://www.acmicpc.net/problem/10992 계속 출력형식이 잘못되었다고 떠서 오래걸렸다. *뒤로 공백문자가 없어야 하는 조건이었다.. #include using namespace std; int Num; int main() { cin >> Num; int L = 2 * Num - 1; for (int i = 1; i < Num; i++) { int cnt = 0; for (int j = 1; j