본문 바로가기

백준

 (224)
백준 2092 - 집합의 개수 icpc.me/2092 1 이상 T 이하의 값을 가진 수 A개가 주어지면 개중에 K개 뽑아서 집합을 만들 때 각 집합의 원소 개수가 S 이상 B 이하인 집합의 개수를 구하는 문제이다. (순서가 다른 것은 같은 것으로 친다.) 이 문제는 푼 사람이 얼마 안되지만 부분집합 개수와 관련된 연산을 하는 문제는 dp의 주요 유형중 하나이다. Solution 일단 A개의 원소들을 각 수가 몇 개 존재하는지 기록하자. 구현에서는 배열을 사용하였다. dp 테이블은 이차원으로 설계한다. dp[n][k] -> n 이하의 값을 가진 수 중에서 k개를 선택해 집합을 생성하는 경우의 수 이때 공집합을 인정하여 dp[0][0] = 1이다. 1부터 T까지 반복문을 돌면서 단일 숫자로 집합을 생성하는 경우(ex {5}, {5, 5}..
백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ ..
백준 11779 - 최소비용 구하기 2 http://icpc.me/11779 출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다. 하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다. 알아야 할 것 최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다. 우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다. 이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다. 구현 최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후, 저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다. 전체 코드 더보기 #include using namespace std; using ll = long lo..
[ICPC] 백준 5719 - 거의 최단 경로 http://icpc.me/5719 Step 1. 최단 경로를 구해보자. 다익스트라를 통해 어렵지 않게 구할 수 있다. 만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자. 노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자. 다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자. Step 2. 도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다. 올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경..
백준 14247 - 나무 자르기 http://icpc.me/14247 날이 지나면서 가장 크게 자라는 나무를 가장 늦게 잘라야 최대한 많은 나무를 얻을 수 있다. 나무가 자라는 양을 기준으로 정렬 후 날짜별로 수확할 수 있는 나무의 양을 계산하면 된다. 전체코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; using pii = pair; using ll = long long; ll res; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector tree(n); for (auto &x : tree) c..

티스토리툴바