Algorithm/동적계획법14 [백준] 9461 파도반 수열 c++ 문제 링크 https://www.acmicpc.net/problem/9461 KEY dp[i] = dp[i-3] + dp[i-2]의 점화식을 찾았다면 쉽게 풀 수 있는 문제이다. 피보나치 수열의 경우 N이 커짐에 따라 빠르게 증가하므로, 반드시 long long 자료형을 써야 한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include #include #include #include #include using namespace std; long long arr[101]; int t,n; int main() { arr[0] = 1; arr[1] = 1; arr[2] = 1; for (int i = 3; i > t; w.. 2023. 3. 23. [백준] 2579 계단 오르기 c++ 문제 링크 https://www.acmicpc.net/problem/2579 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; const int MAX = 301; int n; int stair[MAX]; int dp[MAX]; int main() { cin >> n; for (int i = 0; i > stair[i]; } //dp배열 초기화 dp[0] = stair[0]; dp[1] = stair[0] + stair[1]; dp[2] = max(stair[0], stair[1]) + stair[2]; for (int i = 3; i 2023. 2. 24. [프로그래머스] 정수 삼각형 c++ Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include #include #include using namespace std; const int MAX = 501; int dp[MAX][MAX]; int solution(vector triangle) { int answer = 0; dp[0][0] = triangle[0][0]; for(int i=1;i 2023. 2. 24. [백준] 11055 가장 큰 증가 부분수열 [가장 긴 증가하는 부분수열] 문제와 매우 비슷한(거의 같음) 유형이다. https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분수열을 찾을 때에는 앞의 원소보다 지금원소가 크다면 길이를 1씩 더해가면서 풀었다면, 가장 큰 증가 부분수열을 찾을 때에는 합을 구해가면서 찾는다. 풀이 예시 {1, 10, 2, 5, 20}이런 수열이 있을 때, 1에서 출발한다. 자기자신이므로 합은 1이다. --> dp[1] = 1 10에 도착했다. 10>1을 만족하므로 합은 11이다. --> dp[2] = 11 2에 도착했다. 2와 앞의 원소를 하나씩다 비교하여 최댓값을 골라낸다. 2>1을 만족하므로 합은 dp[1]+2 = 3 --> dp[3] = 3 5에 도착했다. 5와 앞의 원소를 하나씩.. 2022. 2. 19. [백준] 2293 동전1 c++ 그리디알고리즘을 사용한 동전0문제와는 달리 동전1문제는 다이나믹 알고리즘을 사용한다. 점화식 생각이 도저히 안나서 풀이를 참고했는데, 봐도 봐도 헷갈리는 개념이었다. 핵심은 이거다. n번째 동전을 한번 쓴 경우 + n번째 동전을 사용하지 않은 경우 예를 들어서 1, 2, 5원짜리 동전으로 10원을 만들려고 할 때, 5원짜리를 1번 써서 10원을 만든 경우와 5원짜리를 쓰지 않고 10원을 만든 경우로 나눌 수 있다. 이런식으로 계속 내부적으로 나누게 되면 결국 모든 가짓수를 구할 수 있다. 아래 표는 동전단위에 대한 경우의 수를 나타낸 것이다. 그림출처 https://wtg-study.tistory.com/67 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 .. 2022. 2. 18. [백준] 2156 포도주 시식 c++ 문제 링크 https://www.acmicpc.net/problem/2156 KEY [백준] 계단오르기와 상당히 유사한 문제이다. 계단오르기 문제는 항상 연속 몇칸이상을 못간다는 등의 제약조건이 있다. 지금 이 문제 또한 연속 3잔의 포도주를 마실 수 없다는 조건이 있으므로, 현재 시점에서 구할 수 있는 최댓값의 후보를 파악하는 것이 중요하다. 후보는 다음과 같다. 후보1) i-3번째 잔까지의 최댓값 + i-1번째 잔 + i번째 잔 후보2) i-2번째 잔까지의 최댓값 + i번째 잔 후보3) i-1번째 잔까지의 최댓값 다음 후보들 중 최댓값을 구하면 되는 문제이다. 두 문제의 차이점 계단오르기 문제는 지금 칸의 점수를 무조건 포함해야 하기 때문에 후보3이 없어야 한다. 하지만 지금 이 문제의 경우 자신을 .. 2022. 2. 16. 이전 1 2 3 다음
