Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-11-DP-문제-풀이3-1-백준-No2156-포 # C++ #include #include #include using namespace std; int main() { int n; cin >> n; vector d(n); vector a(n); for (int i=0; i> a[i]; for (int i=0; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-11-DP-문제-풀이10-백준-No2156-포도주-시식 # C++(Bottom-up방식 - 2차원 배열 사용) #include #include using namespace std; int arr[10001]; int d[10001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for (int i = 1; i > arr[i]; d[1][1] = arr[1]; // 1잔만 있을 경우 최대 값은 1잔을 마시는 것이므로. d[2][0] = arr[1]; // 2잔만 있을 경우 2번째 자리의 상태..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-10-DP-문제-풀이9-백준-No9465-스티커 # C++(Bottom-up방식) - max함수 쓸 때 STL은 인자 2개만 받는 것으로 정의되어있으니 2개씩 나눠서 해줘야 한다. #include #include using namespace std; int arr[100001][2]; // N번째라는 용어를 사용하여 알고리즘을 생각했으므로 index를 [1~100000][0~1] 를 사용할 수 있도록 함 int d[100001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; for (int..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-9-DP-문제-풀이8-백준-No11057-오르막-수 # C++(Bottom-up방식) #include using namespace std; int d[1001][10]; int main() { int n; cin >> n; // d[1][0~9], "길이가 1이고 0~9로 끝나는 수"에 대한 값 초기화 for (int i = 0; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-8-DP-문제-풀이6-백준-No10844-쉬운-계단-수?category=864321 # C++(Bottom-up방식) #include using namespace std; int d[101][10]; int main() { int n; cin >> n; // n이 1일 때 결과가 9이므로 해주는 초기화 for (int i = 1; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-7-DP-문제-풀이6-백준-No0000-카?category=864321 # C++(Top-down방식) #include using namespace std; long long d[91] = {0}; long long getTwoChinNum(int n) { if ( n 0) return d[n]; else d[n] = getTwoChinNum(n-1) + getTwoChinNum(n-2); return d[n]; } int main() { int n; cin >> n; d[1] = 1; d[2] = 1; cout > n; d[1] = 1; d[2] = 1; for (int i=3; i

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-6-다이나믹-프로그래밍-문제-풀이5-백준-No11052-붕어빵-판매하기-문제 # C++(Top-down 방식) - Top-down방식은 전역변수를 사용해야 구현이 쉽다. - Bottom-up방식에서 2중 for문 중 바깥 for문을 제거하고 j를 i로, i를 n으로 수정했다고 생각하면됨. - 재귀적인 호출이 일어날 때는 두번째 if(d[n] > 0) return d[n]; 을 꼭 넣어줘야 한다.(다이나믹 프로그래밍의 필수적요소) #include using namespace std; int d[1001] = {0}; int p[100001] = {0}; int getMaxPrice(int n) { if(n ..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-5-다이나믹-프로그래밍-문제-풀이4?category=864321 # C++(Top-down 방식) #include using namespace std; int d[12] = {1, 1, 2}; // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0 // d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로 // d[1] = 1; 원래 d[1]은 1이라서. // d[2] = 2; 원래 d[2]은 2이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-4-다이나믹-프로그래밍-문제-풀이3 # C++(Top-down방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[n..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-3-다이나믹-프로그래밍-문제-풀이2 # C++(Top-down 방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[..