728x90 백준브실골/DP45 백준 22871, 징검다리 건너기 개요 문제 링크 실버 1, DP 끝점까지 이동하는 모든 경로마다 필요한 비용의 최솟값 구하기 접근 dp를 사용한다. 들어갈 값은 i번째 까지 갈 때 필요한 비용의 최솟값 갱신하는 경우는 자신보다 앞에 있는 값에 대해 max(앞에 저장된 값, 새로 구한 값)이 더 작은 경우 왜 max(앞에 저장된 값, 새로 구한 값)이냐? 경로를 대표하는 값 = 경로에 필요한 비용의 최대 이고, 우리는 이 대푯값의 최솟값을 구해야 하므로 즉 dp[i] = 경로의 대푯값의 최솟값이고 더 작은 경로를 찾는 경우 갱신한다. 주의할 점 : integer * integer이므로 integer overflow 가능 Pseudo code dp[i] = min_value_till_i 새로 구한 값 = (i-j)*(1+abs(a[i]-a.. 2023. 2. 8. 백준 24392, 영재의 징검다리 개요 문제 링크 실버 1, DP 세 방향 이동이 가능할 때 경로의 수 구하기 접근 단순 2차원 DP. dp[i][j]의 경로는 왼쪽 아래에서 온 것, 아래에서 온 것, 오른쪽 아래에서 온 것의 합 1e9+7 나머지 구할 때 세 수의 합이므로 integer overflow 조심 ex) 1e9+1e9+1e9 = 3e9 > 2^32 Pseudo code left_down = dp[i-1][j-1]; mid_down = dp[i-1][j]; right_down = dp[i-1][j+1]; dp[i][j] = left_down + mid_down + right_down; Source code #include using namespace std; const int R = 1e9+7; int main() { int .. 2023. 2. 8. 백준 25822, 2000문제 푼 임스 개요 문제 링크 실버 1, DP 0이 일정 개수 미만으로 포함된 최장 연속구간의 최댓값 접근 0은 max(2, c/99)까지 가능하다. 3개 값을 저장한 dp를 사용한다. dp[i][j] = i번째까지 j번 스트릭프리즈를 사용한 최대길이 각 dp에 2개의 값을 저장한다. 하나는 길이, 하나는 최댓값 dp를 돌때 값이 0이면 dp[i-1][j-1]과, 0> n; int a[n+1]; for (int i=1; i> a[i]; int dp[n+1][3][2]; for (int j=0; j 2023. 2. 8. 백준 17074, 정렬 개요 문제 링크 실버 1, DP 배열에서 한 원소를 삭제했을 때 배열이 비내림차순인 경우의 수 접근 하나를 삭제하는 것이므로 어떤 전처리를 하고 O(n)을 돌면서 확인해준다. 조건을 생각한다. 제거 후 비내림차순이려면 왼쪽과 오른쪽이 비내림차순이면 된다. i에 대해 b[i]는 1~i까지 비내림차순 여부, c[i]는 i~n까지 비내림차순 여부를 저장한다. b[i-1] && c[i+1]이면 count 증가, 단 왼쪽 원소가 오른쪽 원소보다 작아야 함. Pseudo code b[i] = (1~i) left_ascending_order c[i] = (i~n) right_ascending order if (b[i-1] && c[i+1] && a[i-1] > n; int a[n+2]; a[0] = -2e9; a[n.. 2023. 2. 8. 백준 17216, 가장 큰 감소 부분 수열 개요 문제 링크 실버 1, DP 최장 감소 수열을 구하는 문제, 만약 여러 개가 있으면 합이 가장 큰 수열의 합을 출력한다. 접근 N = 1000이므로 O(N^2)으로 접근 가능 dp를 사용한다. 저장할 값은 i 번째까지의 최대합이다. 갱신은? 앞큰수를 발견하면 max(현재 저장된 값, 새로 갱신될 값)을 해주면 된다. 새로 갱신될 값은? 앞큰수에 현재값을 더한 값이 되겠다. 즉 과거의 최대합 + 자신의 값이 저장된 값보다 더 큰 경우 갱신 Pseudo code dp[i] = max_sum_value; if (앞큰수 발견) new_sum_value = dp[앞큰수]+a[i] dp[i] = max(dp[i],new_sum_value) Source code #include using namespace std.. 2023. 2. 8. 다음 728x90