Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-21-DP-문제-풀이4-4-백준-No2225-합분해?category=864321 # C++ #include using namespace std; long long d[201][201]; int main() { int n, k; cin >> n >> k; d[0][0] = 1; for (int i = 1; i

합분해 문제 * 어려워서 깊은 이해는 못하겠지만 암기는 할 수 있을 듯 하다. - https://www.acmicpc.net/problem/2225 문제요약 N과 K값이 주어지면 0~N의 수 K개로 N을 나타낼 수 있는 모든 경우의 수를 구하고 그 수를 1,000,000,000로 나눈 나머지를 출력하라. 해결 방법 1. D 정의 D[K][N] = "K개의 수를 더해서 합이 N이 되는 경우의 수" 마지막 항이 L값을 가진다면 이전 항들의 합은 N-L임 그리고 L을 분리시킨다면 K-1개의 수를 더해서 합이 N-L이 되는 경우의 수가 됨. 따라서, D[K][N]은 다음의 점화식으로 구할 수 있음 이렇게 맨 뒤의 항을 하나씩 분리시키는 과정이 반복될 때 'K'와 'N'을 입력받으면 K는 1~'K' 의 범위를 가..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-20-DP-문제-풀이4-3-백준-No9461-파도반-수열 # C++ /*방법1*/ #include using namespace std; long long d[101]; int main() { int T; cin >> T; while(T--){ int n; cin >> n; d[1] = 1; d[2] = 1; d[3] = 1; d[4] = 2; d[5] = 2; for (int i = 6; i > n; d[1] = 1; d[2] = 1; d[3] = 1; for (int i = 4; i

파도반 수열 문제 - https://www.acmicpc.net/problem/9461 문제요약 삼각형으로 나선을 만드는데 변의 길이가 1인 정삼각형에서 시작한다. 다음 삼각형은 지금까지 만들어진 나선에서 가장 긴 변에 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1) ~ P(12) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 P(N)의 값을 출력하는 프로그램을 작성해라. 해결 방법 1. D[i] 정의 생략. 2. 점화식 세우기 방법1. 직감으로 본뒤 점화식이 옳은지 확인 P(12) = 12, P(11) = 9, P(7) = 3 에서 볼 수 있듯이 P(12) = P(11) + P(7) 이다. 또한, 이러한 패턴을 다른곳에서도 보여준다. 따라서,..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-19-DP-문제-풀이4-2-백준-No2133-타일-채우기 # C++ #include using namespace std; int d[31]; int main() { int n; cin >> n; d[0] = 1; for (int i = 2; i = 0; j+=2){ if(j == 2) d[i] = 3 * d[i-j]; else d[i] += 2 * d[i-j]; } } cout

타일 채우기 문제 - https://www.acmicpc.net/problem/2133 문제요약 3 x N의 타일을 1 x2, 2 x 1 타일로 채우는 방법의 수 구하기 해결 방법 1. D[i] 정의 D[N] = "3 x i 를 채우는 방법의 수" 2. 점화식 세우기 N번째에 올 수 있는 경우의 수를 모두 조사해 봐야 한다. 길이가 2인경우, 4인경우. 6인경우, ... 모두 다른 경우의 수이다. ... ... 따라서 D[i] = 3D[i-2] + 2D[i-4] + 2D[i-6] + ... (i-k >= 0 일 동안) 이다. 타일의 모양상 i가 홀수일 때는 채우지 못하므로 i는 짝수이어야 한다. (1)시간복잡도 = for 문의 반복 횟수 (2) 구현 -> 'for문을 이용한 반복문'으로 구현 #inclu..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-18-DP-문제-풀이4-1-백준-No1699-제곱수의-합 # C++ #include using namespace std; int d[100001]; int main() { int n; cin >> n; for (int i = 1; i

제곱수의 합 문제 - 백준 No.9095 : 1, 2, 3 더하기 문제와 비슷함 - https://www.acmicpc.net/problem/1699 문제요약 어떤 자연수 N이 주어지면 이를 N보다 작은 제곱수의 합으로 나타내는 데, 이때의 항의 최소개수를 구해라. 해결 방법 1. D[i] 정의 D[N] = "자연수 N을 제곱수의 합으로 나타내는데 이때의 항의 최소개수" 2. 점화식 세우기 정수 N이 주어지면 앞에 어떤 조합들이 오고 맨 뒤에 i^2이 온다고 해보자. O + O + O + ... + i^2 = N 이 된다. 여기서 i^2를 제외시킨 앞의 나머지 항들에 대해서만 생각해보면 D[N] = min(D[N - i^2] + 1) 가 된다. i^2 이 1^2, 2^2, 3^2, ,.....이 될 수 ..

연속합 문제 - https://www.acmicpc.net/problem/2579 문제요약 * 2156번 포도주 시식 문제랑 비슷하게 생각하면 된다. 그냥 숫자가 나열된 문제로 볼 수 있음. 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 각 계단에는 점수가 쓰여 있는데, 올라가면서 계단을 밟으면 계단에 쓰여있는 점수를 얻게 된다. 계단을 오르는 데는 다음과 같은 규칙이 있다. 1) 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있다. (즉, 한 계단을 밟으면 이어서 다음 계단이나 다다음 계단으로 오를 수 있다.) 2) 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 3) 마지막 도착 계단은 반드시 밟아야 한다. ex) s..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-17-DP-문제-풀이3-6-백준-No2579-계단-오르기 # C++(2차원 배열) #include using namespace std; int a[301]; int d[301][3]; int main() { int n; cin >> n; for (int i = 1; i > a[i]; d[1][1] = a[1]; d[1][2] = 0; d[2][1] = a[2]; d[2][2] = a[1] + a[2]; for (int i = 3; i