Study hard

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복�� www.acmicpc.net ☆가로 길이가 2 늘어날 때마다 케이스가 2개씩 더 늘어난다. ※점화식※ dp[0] = 1 (추가 케이스 더할 때 필요) dp[1] = 0 dp[2] = 3 dp[x] = 3 * dp[x-2] + 2 * dp[x-4] + ··· + 2 * dp[0] (마지막 항은 추가케이스 2개 더하는 항) #include using namespace std; int N; long ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net ※점화식※ dp[i] : i를 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수 dp[x] = dp[x-j^2] + 1 (j^2는 x값에 가장 가까운 제곱수, 자연수 x-j^2에 j^2 더한 항의 수) #include using namespace std; int N; long long dp[100001]; void DP() { for (int i = 1; i

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 앞의 계단을 선택했느냐 안했느냐가 다음 계단 선택에도 영향을 끼친다. 그래서 이차원 배열을 이용하여 계단을 선택했을 때와 안 했을 때를 나누어 최댓값을 구했다. ※점화식※ dp[i][0] : i번째 계단을 첫 계단으로 하고, 선택하지 않을경우 점수의 최댓값 dp[i][1] : i번째 계단을 첫 계단으로 하고, 선택할 경우 점수의 최댓값 dp[n][1] = Stair[n] dp[n - 1][0] = dp[n][..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net * 연속된 수를 선택해야 하며, 수를 한 개 이상 선택해야 한다. = 바로 직전 수까지의 연속합에 현재 값을 더하는 게 현재 값보다 큰지 비교하여 dp에 저장 ※점화식※ dp[i] : i번째 수를 마지막으로 연속합에 포함시킬 때 나올 수 있는 가장 큰 값 dp[1] = A[1] dp[x] = max(dp[x-1] + A[x], A[x]) #include #include //max using namespace..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 두 개의 dp배열이 필요하다. 하나는 각각 숫자들의 앞에서 증가 수열의 길이를 저장하는 dp_front, 다른 하나는 각각 숫자들의 뒤에서 감소 수열의 길이를 저장하는 dp_back으로 했다. dp_front[i] : i를 마지막 숫자로 했을 때 가장 긴 증가 부분 수열 dp_back[i] : i를 시작 숫자로 했을 때 가장 긴 감소 부분 수열 모두 구하고, 인덱스마다 dp_front[x] + dp_back[x] -..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 2020/06/09 - [백준/DP] - (c++)백준 11053번: 가장 긴 증가하는 부분 수열 위 문제와 거의 똑같다. 부등호 하나만 바꿔주면 된다. #include using namespace std; int N; int A[1001]; long long dp[1001]; void DP() { long long M..