Storage Gonie

문제 풀이 자세한 풀이 : 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

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-16-DP-문제-풀이3-5-백준-No1912-연속합 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d(n); for (int i = 0; i > a[i]; d[0] = a[0]; for (int i = 1; i < n; i++) d[i] = max(d[i-1] + a[i], a[i]); cout

연속합 문제 - https://www.acmicpc.net/problem/1912 문제요약 n개의 정수로 이루어진 임의의 수열이 주어지면 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하라. ex) A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 연속된 수들의 합 중 가장 큰 값은 12 + 21 = 33 해결 방법 1. D[i] 정의 D[i] = "A[i]로 끝나는(까지 왔을 때의) 최대 연속합" 으로 정의할 수 있고, A[i]로 끝나는 최대 연속합은 두가지의 경우가 될 수 있다. 1) A[i-1]로 끝나는 최대 연속합에 A[i]가 포함되는 경우 => D[i-1] + A[i] 2) A[i]가 새로운 수열의 합으로 시작하는 경우 => A[i] 그러면 ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-15-DP-문제-풀이3-4-백준-No11054-가장-긴-바이토닉-부분-수열 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d1(n); vector d2(n); for (int i = 0; i > a[i]; // 왼->오 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기 for (int i = 0; i < n; i++) { d1[i] = 1; for (int j = 0 ; j < n; j++) { if (a[j] < a[..

가장 긴 바이토닉 부분 수열 문제 - https://www.acmicpc.net/problem/11054 문제요약 수열 A가 주어졌을 때, 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {1 5 2 1 4 3 4 5 2 1} 가장 긴 바이토닉 부분 수열 A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} => 길이는 7 해결 방법 * 최근에 푼 3개의 문제에 대한 이해가 있다면 이를 응용하여 풀 수 있다. - 바이토닉 수열의 꼭지값을 기준으로 왼쪽은 가장 긴 증가하는 부분 수열, 오른쪽은 가장 긴 감소하는 부분 수열을 찾아 이 둘의 길이를 합하여 구할 수 있다. 이를 조금만 다르게 생각해보면 "부분 수열의 마지막 원소로 A[i..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-13-DP-문제-풀이3-3-백준-No11722-가장-긴-감소하는-부분-수열 # C++(reverse해서 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 사용) #include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); vector d(n); for (int i = 0; i > a[i]; // 역순으로 변경 reverse(a.begin(), a.end()); // 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용 for (int i = 0; i < n; i++) { d[i]..

가장 긴 감소하는 부분 수열 문제 - https://www.acmicpc.net/problem/11722 문제요약 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하는 문제 부분 수열이란? 수열에서 일부를 선택한 수열이다. ex) A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열 A = {10, 30, 10, 20, 20, 10} => 길이는 3 해결 방법 * 바로 전전 문제를 조금 수정해서 풀 수 있다. 방법 1. 입력으로 주어진 수열을 reverse해서 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' 방법 2. 왼쪽 -> 오른쪽 순으로 값을 구하는 것이 아닌, 오른쪽 -> 왼쪽 순으로 '가장 긴 증가하는 부분 수열의 길이를 구하는 방법' (1) 구현..