DP14 [백준] 2419 - 사수아탕 (c++) https://www.acmicpc.net/problem/2419문제 요약n개의 사탕바구니 위치가 주어진다. 각 사탕 바구니에 사탕이 m개 씩 들어있다. 아직 먹지 않은 사탕 바구니에 사탕이 1시간당 1개씩 녹는다. 1이동 하는데 1시간이 들때, 0에서 시작해서 먹을 수 있는 최대 사탕 개수를 구해라. 풀이 (N^3)DPdp배열은 dp[n][n][2]; dp[i][j][isr] i번 부터 j번 바구니까지 모두 먹었고 현재 위치가 isr==false면 i 아니면 j 이렇게 구성한다. 현재까지 혹은 현재부터 먹을 사탕을 최대화하는 문제로 보기 쉬운데 경과시간을 모르기 때문에 그렇게 해선 최적으로 만들 수 없다. 발상의 전환이 필요한데 바로 녹을 사탕 개수를 최소화 하는 것이다. 그렇다면 녹을 사탕 개수를 .. 2025. 1. 10. [백준] 1126 - 같은 탑 (c++) https://www.acmicpc.net/problem/1126 문제 요약블록 N개의 길이가 주어진다. 블록으로 높이가 같은 두 탑을 만들 때 최대 높이를 구해라. *블록을 모두 사용하지 않아도 된다. 풀이 (N*1e6)DPdp[n][1e6] dp[i][j] = i블록까지 사용했고 두 탑의 높이 차가 j일때 더 높은 탑의 높이 로 정의하고 채워주면 된다. -1로 초기화를 하고 불가능한 경우는 continue 했다. 블록을 쓰지 않아도 되기 때문에 dp[i-1][j]->dp[i][j]로 전파를 해준다.#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend.. 2025. 1. 7. [백준] 1006 - 습격자 초라기 (c++) https://www.acmicpc.net/problem/1006 문제 요약그림과 같은 두줄짜리 환형 건물이 있다. 각 구역마다 배치된 적의 수가 주어진다.구역마다 소대를 침투시킬 것이다. 한 소대엔 w명이 있고 두 구역 적의 수 합이 w보다 작거나 같으면 인접한 두 구역까지 침투할 수 있다. 모든 구역에 소대를 침투시키기 위해 필요한 최소 소대 수를 구해라.풀이 (N)DP환형을 처리하는게 정말 까다로운 문제였다. 일단 선형 문제라 생각하고 풀어보자. dp[n][3] dp[i][j] = i-1까지 모두 커버 했고 i의 상태가 j일때 최소 소대 수 라고 정의하고 채워주면 어렵지 않게 풀 수 있다. 1열과 n열을 잇는 경우의 수를 모두 base case로 만들어 한 번씩 돌려보면 환형 문제를 해결할 수 있.. 2025. 1. 7. [백준] 3233 - BRODOVI (c++) https://www.acmicpc.net/problem/3233Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 4번 문제 요약N크기의 강에 칸 마다 물고기에 개수가 주어진다. M개의 닻을 내릴 위치와 배의 크기가 주어질 때 배를 닻에서 벗어나지 않게 옮겨서 잡을 수 있는 물고기의 최댓값을 구해라. 풀이 (MlogM)스위핑DP누적합닻을 스위핑하면서 1차원 DP배열을 업데이트 해주면 된다. 배가 서로 겹칠 수 없기 때문에 현재 배가 전,후 닻까지 가지 못하게 하고 범위안에서 누적합으로 잡을 수 있는 물고기를 구해 업데이트 해준다. 배가 가지 못하는 곳도 생기기 때문에 갱신 했던 마지막 위치 부터 현.. 2024. 10. 31. [백준] 26268 - 은?행 털!자 2 (c++) https://www.acmicpc.net/problem/26268 문제 요약N개 은행에 대하여 (좌표, 은행을 털 수 있는 시간, 털었을 때 얻는 돈)이 좌표 순으로 주어진다. 0부터 1시간에 +1씩 움직일 수 있을 때 얻을 수 있는 최대 금액 출력해라. 풀이 1 (NlogN)DP세그먼트 트리순서대로 봤을 때 Ti-Xi#include using namespace std;#define ll long long#define mid (st+en)/2ll tree[1500001];ll Update(int n, int st, int en,int i,ll val) { if (st > i || en r || en = l && en sync_with_stdio(0); int n;cin>>n; .. 2024. 9. 1. [백준] 29200 - 문제 수 줄이기 (c++) https://www.acmicpc.net/problem/29200 문제 요약N크기의 수열이 주어진다. 수열을 구간으로 분할하는데 인접한 수열끼리 크기가 같으면 안 된다. 수열끼리 xor한 값의 합이 최대가 되도록 분할하고 합을 출력해라. 풀이 (N)DP애드혹일단 xor은 각 비트 자리에 1이 단 하나만 있어야 비트가 켜지기 때문에 잘게 쪼갤 수록 이득이란 걸 알 수 있다. 언뜻 보고 1,2,3 크기로만 분할해서 최댓값을 만들 수 있을 줄 알았지만6 1 1 2 4 8 8이런 반례 케이스가 있었다(3까지 포함하면 22, 4까지 포함하면 24 나옴). 4까지 포함하니 최댓값을 만들 수 있었다. 제한시간이 넉넉해서 한 1~10까지 써도 상관은 없다. 제한적인 숫자로 최댓값을 구성할 수 있다는 걸 직감을 통해 .. 2024. 8. 28. 이전 1 2 3 다음
