DP14 [백준] 3321 - 가장 큰 직사각형 (c++) https://www.acmicpc.net/problem/3321 문제 요약0또는1로 이루어진 N*M크기의 행렬이 주어진다. 열끼리 순서를 바꿀 수 있을 때 1로 이루어진 직사각형의 최대 넓이를 구해라. 풀이 (NM)DP그리디밑변 행을 고정시켜 보자. 모든 열에 대해 높이를 내림차순 배열로 갖고 있으면 순회하며 (i*현재 높이)를 모두 구해 최대 넓이를 구할 수 있다.매번 퀵소트를 해주면 시간초과가 나기 때문에 O(N) 정렬 방식을 사용해야 한다. 직전 오름차순 배열에서 현재 값이 0이면 맨 뒤로 보내는 방법을 통해 정렬을 O(N)에 해결할 수 있다.#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#defin.. 2025. 4. 29. [백준] 26105 - Folding Stick (c++) https://www.acmicpc.net/problem/26105 문제 요약n개의 막대 길이가 주어진다. 각 i,i+1번째 막대는 힌지로 연결되어 있고 한 방향으로만 접을 수 있다. 막대를 접어서 만들 수 있는 최소 길이를 구해라. 풀이 (NlogN)DP우선순위 큐막대를 접었을 때 접힌 부분에 포함되는 힌지는 접을 수 없게 된다. dp[i]를 i번째 힌지를 접었을 때 최소 접힌 부분 길이라고 한다면 dp[i]는 pos[j]+dp[j]#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()#define mid (st+en>>1)int main() { .. 2025. 3. 27. [백준] 25948 - Islands Tour (c++) https://www.acmicpc.net/problem/25948ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2022 F번 문제 요약정점 N개 간선 M개의 방향 그래프가 주어진다. 그래프에서 각 정점에서 나가는 간선은 최대 한개이다.한 정점을 두 번 이상 방문하지 않는 최장경로를 구해라. 풀이 (M)위상정렬DP그래프의 각 컴포넌트는 사이클을 최대 한개 포함하고 있다. 위상정렬 DP를 통해 사이클을 이루지 않는 간선들만 포함하는 최장경로를 구하고, 남은 간선들에 대해 DFS로 사이클의 크기를 구해서 경로에 붙혀주면 된다.#include usin.. 2025. 1. 28. [백준] 6611 - Simon the Spider (c++) https://www.acmicpc.net/problem/6611 문제 요약정점이 N개 간선이 M개인 그래프가 주어진다. 그래프의 간선들로 스패닝 트리를 만들어야 한다.쓴 간선들 중 가장 비싼 간선의 가중치는 -가 될 때, 스패닝 트리를 만드는 최소 비용을 구해라. 풀이 (N^3)MSTDP일단 MST를 하나 구성한다. 간선 i에 대해 i가 가장 큰 간선이라 가정하고 MST에 삽입시킨다. 이 때 생기는 사이클에 가장 큰 간선을 하나 지운다. 이걸 모든 i에 대해 취해주며 min값을 구해주면 된다.DFS로 사이클에서 가장 큰 간선을 찾아주는 O(NM) 풀이를 할 수도 있고, DP로 전처리 해줘도 된다.난 DP로 전처리 하는 방법을 사용했다.#include using namespace std;#define l.. 2025. 1. 27. [백준] 5898 - Nearby Cows (c++) https://www.acmicpc.net/problem/5898 문제 요약정점이 N개인 트리가 있다.정점 i에 소가 C(i)마리 있다. 모든 i에 대해 간선을 최대 K개 거쳐 i에 올 수 있는 소가 몇마린지 구해라. 풀이 (NK)DPdp[i][j]를 최대 j개의 간선을 거쳐 i로 올 수 있는 소의 수라고 정의해보자. i와 인접한 정점 v에 대해 dp[v][j-1]를 모두 더해주고 겹지는 만큼 빼주면 된다.#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); int n,k;cin>>n>>k; vector adj[n+1]; int c[n+1]; for(int .. 2025. 1. 27. [백준] 32191 - 그래프의 종착지 (c++) https://www.acmicpc.net/problem/32191 문제 요약 조건을 만족하는 그래프가 주어진다. t번째 턴에 마지막으로 도착한 노드의 번호를 구해라.풀이 (N)위상정렬DP수학노드의 방문 횟수를 알면 어떤 자식노드를 가르키고 있는지 알 수 있다. 부모노드의 방문 횟수를 알면 자식노드의 방문 횟수를 알 수 있다. 두가지 성질을 활용해 문제를 해결 할 수 있다. 입력 받은 그래프를 DAG로 바꿔준다. 위상정렬을 한 번 돌려주면서 t-1번째 턴까지 실행 했을 때 방문횟수를 저장하는 dp배열과 방향을 저장하는 배열을 업데이트 해준다. 마지막 t번째 턴은 직접 실행하면서 마지막 노드를 구한다. 부모 노드가 여러개 있을 수 있다는 점을 유의해야 한다. #include using name.. 2025. 1. 11. 이전 1 2 3 다음
