본문 바로가기
728x90

백준브실골/DP45

백준 11909, 배열 탈출 개요 문제 링크 골드 5, DP 큰 값에서 작은 값으로, 크지 않은 경우 크게 만들면서 이동할 때의 최소비용 접근 단순 2차원 경로탐색 문제, 경로탐색 문제는 항상 그 점을 경로를 통해 구성할 수 있는, 즉 그 점의 이전점이 될 수 있는 위나 왼쪽을 비교하는 것이 정석이므로 어렵기가 쉽지 않다. 이때 비용이 추가되므로 dp[y][x]에 들어가는 것은 (y,x)까지 오는 데 들인 비용, 갱신은 어떻게? 위에서 내려올 때 든 비용 혹은 왼쪽에서 이동할 때 든 비용 이때 비용을 추가할때는 유효한 경우만 해야 하는데, 유효한 경우란? 왼쪽을 예로 들면 비용 = 현재 위치의 값 + 1 - 왼쪽값 >= 1 인 경우이다. Pseudo code cost[i][j] 양수만(값차이) { if (값차이 >=1) return.. 2023. 2. 11.
백준 17265, 나의 인생에는 수학과 함께 개요 문제 링크 골드 5, DP 사칙연산을 수행하며 경로를 이동할 때 최종값의 최대최소 접근 단순한 2차원 경로탐색 dp인데, 문자열이 들어가면서 + 최대최소를 모두 물어보면서 까다로워진 케이스. dp[i][j]에는 (i,j) 까지 오면서 얻은 최댓값을 저장하고, 업데이트는 어디와 비교하느냐? 하면 세 지점과 비교하면 됨. 왼쪽위, 두칸 왼쪽, 두칸 위. 나머지는 크게 복잡한 것이 없고 실수만 안하면 됨 Pseudo code for (y = 세로) for(x = 가로) left_up = dp[y-1][x-1] 연산자 dp[y][x] two_left = dp[y][x-2] 연산자 dp[y][x] two_up = dp[y-2][x] 연산자 dp[y][x] dp[y][x] = max_or_min(left_up.. 2023. 2. 9.
백준 2229, 조 짜기 개요 문제 링크 골드 5, DP 최댓값과 최솟값의 차이의 합이 최대가 되도록 연속부분집합을 구성하기 접근 여러개의 집합을 구성해야 하니까 2차원 dp가 필요한가? 했는데 1차원으로 충분했음. 우선 dp와 그 업데이트 부터 생각하자. dp에는 답이 될 최대 값를 저장한다. 그럼 업데이트는? 앞에서부터 보면서 최대 값 + 더해질 값이 더 큰 경우 업데이트 하면 된다. 말이 애매한데 예시를 보자. i 1 2 3 4 5 a[i] 2 5 7 1 3 dp[i] 0 3 5 9 ? set {2} {2,5} {2,5,7} {2,5},{7,1} =3+6 각 집합을 보면 4까지 잘 이해가 된다. 이때 i=5라고 하자. 5일때는 i=1부터 4까지 비교를 한다. 어떻게 비교하냐? 하면 이렇게 생각해보자 // i=1과 비교 {2.. 2023. 2. 9.
백준 14309, Safe Squares (Large) 개요 문제 링크 골드 5, DP 2차원 배열 내에서 0으로 이루어진 정사각형의 개수 접근 한 변의 길이가 여러 개인 정사각형을 모두 세 주어야 하는데 그럼 O(n^2)을 넘어가지 않나? 하고 생각. 일단 dp를 쓰고 O(n^2)안에 해결하는 방법은 인접한 것들만 봐줘야 하는데, 어디까지 보냐가 핵심. dp에 저장할 내용은 왼쪽 위부터 만들어 내려올 수 있는 최대 정사각형의 길이 이게 되는 이유는 (x,y)까지의 최대 길이가 곧 (x,y)를 오른쪽 아래점으로 포함하는 정사각형의 개수가 됨. 왜냐하면 최대 길이 정사각형 내부에서는 모두 정사각형을 만들 수 있으니까. 왼쪽이랑 위는 반드시 봐줌. 최대 정사각형은 왼쪽과 위에서 만든 정사각형을 반드시 포함하기 때문. 이때 아래 케이스를 보자 011 112 12?.. 2023. 2. 9.
백준 23317, 구슬 굴리기 개요 문제 링크 골드 5, DP 지점을 반드시 통과하며 좌우를 선택하여 이동하는 경로의 수 접근 우선 주어진 지점들을 통과해야 하니까, (0,0) 출발점에서 m번째 지점까지 순차적으로 이동하면 됨. 마지막에는 이동가능한 (n,x)의 모든 점으로 이동하는 경로 곱해주면 됨. (b,a)에서 (y,x)까지 이동하려면 어떻게 해야하나? 하면 조합 써주면 됨. (b,a)에서 (y,x)까지는 전체 이동이 |b-y|번, 그 중 왼쪽 이동이 |a-x|번 필요함. 즉 comb[dy][dx] 해주면 됨. 이때 이동이 불가능 한 경우를 고려하면 (b,a), (y,x)에서 x가 a보다 작거나, x가 a+dy보다 크면 이동 불가. 이외에도 b==y이면 이동 불가 하기도 한데 x가 a보다 작은 경우를 제외하고는 comb[dy][.. 2023. 2. 8.
백준 25634, 전구 상태 뒤집기 개요 문제 링크 골드 5, DP 연속된 부분 수열의 상태 변경을 통합 누적합의 최댓값 접근 아무래도 어렵게 짜는데 도가 튼 듯 하다. 처음에는 연산을 한 전구에만 수행하는 줄 알았는데, 연속한 구간에 대해 한 번 수행한다는 것을 알고 뇌정지 옴. 세그트리인가? 하는 생각이 스쳐지나가고 그랬음. dp를 쓰는데, dp[i][0]은 i까지 연산을 안 쓰고 온 합, dp[i][1]은 i까지 연산을 연속된 구간에 쓰면서 온 합의 최댓값으로 했다. dp[i][0]은 단순 누적합이라 아래처럼 해주면 됨. dp[i][0] = dp[i-1][0] + a[i]*b[i] 그러면 dp[i][1]은? 이 부분을 원래 골5정도면 쉽게 주는데 개인적으로 이런 문제를 안접해봐서 그런지 어렵게 짰음. dp[i][1] = max(dp[.. 2023. 2. 8.
백준 25343, 최장 최장 증가 부분 수열 개요 문제 링크 골드 5, DP 2차원에서 최단경로의 증가 부분수열의 최대 길이 접근 LIS를 2차원으로 확장시킨 문제, 1차원 LIS의 O(N^2)을 2차원에 잘 응용하면 O(N^4)에 할 수 있는데, N=100이라서 1억번 연산안에 잘 해결할 수 있다. LIS의 기본 원리 = 만약 앞작수를 발견하면 최대길이[앞작수]+1과 비교해 업데이트 한다를 2차원에 적용시켜보자. 2차원에서 앞이란 무엇일까? 바로 왼쪽 위다. 최단경로로 이동할 때는 오른쪽이나 아래만 이동하므로, 결국 어떤 지점까지 도달하려면 왼쪽이나 위를 거쳐올 수밖에 없기 때문이다. 그래서 왼쪽 위 영역에 대해 업데이트를 진행하면 된다. 이때 입력값이 양수이므로 1-n까지 입력을 받고 a[y][0]과 a[0][x]를 0으로 초기화하면 모든 지점.. 2023. 2. 8.
백준 16494, 가장 큰 값 개요 문제 링크 골드 5, DP M개의 부분집합의 총 합의 최댓값 접근 2228번과 거의 완벽히 동일하다. 부분집합이 연속하지 않기 때문에 for문의 범위가 약간 달라지는 것빼고는 코드까지 동일하다. 따라서 접근은 2228번으로 대체한다. Pseudo code dp[i][k] = 끝이 i이고 k개 집합을 쓴 최대 합 for(k = 집합 사용개수) for (j = i의 앞 = k-1개 사용한 부분) for (r = j의 뒤 i의 앞 = 부분합을 구할 부분) if (j까지 k-1개 사용 + sum[r~i]가 더 작으면) 업데이트 Source code #include using namespace std; int main() { int n, m; cin >> n >> m; int a[n]; int sum[n][.. 2023. 2. 8.
백준 25289, 가장 긴 등차 부분 수열 개요 문제 링크 골드 5, DP 부분 수열 중 가장 긴 등차 수열의 길이 접근 LIS를 쓰는 문제인가? 했다가 골드5에 O(nlogn)을 묻지는 않을 것 같아서 pass. A가 100까지면 아하, A를 중심으로 루프를 돌려야 하는구나. dp[i][j] 에 들어가는 건 공차가 i이면서 끝값이 j인 등차수열의 최대 길이 업데이트는? 등차수열의 이전항이 끝값인 경우의 최대 길이 + 1 해주면 됨. 즉, dp[i][j] = dp[i][j-i]+1 주의할 점은 음수 공차도 되므로 음수 인덱스 방지를 해줘야 하는 것. Pseudo code for (i = 0~n) for (j = -A~A) v = a[i] dp[j][v] = dp[j][v-j]+1 answer = max(dp) Source code #include.. 2023. 2. 8.
백준 24430, 알고리즘 수업 - 행렬 경로 문제 7 개요 문제 링크 골드 3, DP 최대 이득 경로에 포함되는 특정점의 개수의 최댓값 구하기 접근 단순한 2차원 dp, 우선 dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])을 이해하고 있어야 한다. 이유는 (현재 최대 이득) = (현재 추가되는 이득) + (과거 최대 이득) 특정점의 수는 어떻게 구하냐, 만약 왼쪽과 위의 이득이 다르면 무조건 큰 쪽의 특정점을 더해준다. 이유는 이득을 최대화하는 것이 특정점의 수를 최대화 하는 것보다 우선되기 때문. 그리고 왼쪽과 위의 이득이 같다면 특정점의 수가 더 큰 쪽을 더해준다. Pseudo code 이득[현재] = max(이득[왼쪽], 이득[위]) + 추가이득[현재] if (이득[왼쪽] == 이득[위]) 특정점[현재] += m.. 2023. 2. 8.
728x90

티스토리툴바