목록백준 (183)
Study hard
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 0은 첫번째 자리에 올 수 없다. 2. 1은 앞에 0이 있어야 나올 수 있다. ※점화식※ dp[i][j] : i번째 자리가 j일 때 이친수 개수 dp[1][0] = 0 (첫번째 자리에 0 올 수 없다.) dp[1][1] = 1 dp[x][0] = dp[x-1][0] + dp[x-1][1] (x번째 자리에 0이 오면 그 앞은 0과 1 모두 있을 수 있다.) dp[x][1] = dp[..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 뒤에 오는 숫자를 신경써야 한다. 9 다음의 수는 9밖에 올 수 없다. ※점화식※ dp[i][j] : i번째 자리에 j가 올 때 경우의 수 ※i=N부터, j=9부터 점화식 따라가기 if(j==9) dp[i][j] = dp[i+1][j] (j가 9이면 다음 숫자는 9밖에 못 온다.) else dp[i][j] = dp[i][j+1] + dp[i+1][j] (9가 ..
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]의 경우의 수로 채워짐 점화식 ..