DP37 백준 15678 / C++ https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net [ 풀이 ] dp[j]=max(0, dp[k])+a[j] 이다. (단, k>=j-D , k qe || e > D; for (int i = 1; i > K[i]; ll ans = K[1]; upd(1, 1, n, 1, K[1]); for (int i = 2; i 2022. 8. 2. 백준 3114 / C++ https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)까지 왔을 때 합의 최댓값이라 하자. dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]에서 올 수 있다. 앞의 두 경우는 이전dp값에다 현재 (i,j)에서 위아래로 바나나와 사과개수를 더해주면 된다. 이미 각 열에 대한 바나나의 합과 사과의 합을 전처리해놓자. dp[i][j-1]에서 오는 경우는 만약 (i,j)가 사과였다면.. 2022. 8. 2. 백준 13555 / C++ https://www.acmicpc.net/problem/13555 13555번: 증가하는 부분 수열 길이가 N인 수열 A1, A2, ..., AN와 정수 K 주어진다. 이때, 수열 A의 부분 수열 중에서 길이가 K이면서 증가하는 부분 수열의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] naive하게 세워보자. dp[i][j]를 A1~Ai까지 길이 j인 증가 부분수열의 개수라고 하자. dp[i][j]=sum(dp[k][j-1])이 된다. (단, a[k] n >> k; for (int i = 1; i > a[i]; for (int i = 1; i 2022. 8. 2. 백준 1126 / C++ https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net [ 풀이 ] dp를 세워보자. 우선 인덱스는 필수조건이다. 그리고 높이를 알아야 하는데 두개의 높이를 모두 저장할 수 없다. 한 개의 높이만을 저장한다면 나머지 역시 알 수 없다. 높이의 차이를 저장하면 깔끔하게 해결된다. dp[i][j]를 i번 블록을 선택할지 정하려하고 현재 높이차가 j일 때 두개의 높이중 큰 값이라고 정의하자. 상태전이는 3가지이다. 1. i번 블록을 선택하지.. 2022. 8. 2. 이전 1 ··· 4 5 6 7 8 9 10 다음