코딩테스트 준비/PS (21) 썸네일형 리스트형 C++ 백준 17404 (RGB거리 2) 백준 17404 (RGB거리 2) https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 백준 1149(RGB거리)의 응용버전이다. 1149번 RGB거리에 대한 설명은 여기(링크)에 있으니 DP관점의 해결방법을 알고오자. 기존 1149번(이하 RGB거리1)문제와 달리 하나의 조건이 추가되었다. 처음집과 마지막집의 색이 달라야 한다는 것이다. RGB거리1에서는 처음과 마지막은 고려하지 않았기 때문에 한번의 DP과정.. C++ 백준 1149 (RGB거리) 백준 1149 (RGB거리) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 전형적인 DP문제이다. 설명 문제를 보면 다음단계의 집색깔은 전단계의 집색깔과 같을 수 없다. 한단계 한단계 나아가며 현재단계에서의 optimal solution은 전단계의 optimal solution과 관계가 있다. 이 말은 dynamic programming을 통해 이문제를 해결할 수 있다는 것이다. 예를 들면 현재 네번째 집의 색이 R이라면.. C++ 백준 1948 (임계경로) 백준 1948 (임계경로) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 설명 이 문제는 임계경로의 길이와 그 경로들에 채택되었던 간선의 개수를 세는 문제이다. 임계경로의 길이를 구하는 방법은 여기(링크)에 있다. 임계경로는 하나만 존재하는 것이 아니라 여러개 존재할 수도있다. 때문에 이 임계경로들에 채택되었던 간선의 개수를 세는 방법은 꽤 어려웠다. 여러 방법을 통해 임계경로들에 채택되었던 간선의 개수를 셀 수 있.. C++ 백준 1647 (도시 분할 계획) 백준 1647 (도시 분할 계획) https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 설명 이 문제는 MST를 찾는 문제이다. MST를 찾기 위해 크루스칼 알고리즘을 사용해야하는데 이에 대한 자세한 설명은 여기(링크)에 있다. 연결되어있는 여러 도시를 가장 작은 MST 두개의 그룹으로 나누는 것이 문제의 목표이다. 때문에 주어진 그래프의 MST로 찾은 후에 찾은 MST중 가중치가 가장 큰 엣지만 제거한다면 문제.. C++ 백준 2252 (줄 세우기) 백준 2252 (줄 세우기) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 설명 이 문제는 위상정렬(DFS)를 통해 간단히 풀 수 있는 문제였다. 위상정렬에 대한 설명은 위상정렬(링크)에 자세히 설명이 되어있다. 예제입력으로 각 일에 대한 순서들이 주어지는데 각 일을 하나의 노드로 생각하고 방향성이 있는 그래프로 생각하면 된다. 예를 들어 1 2 가 입력되었다면 1번노드에서 2번노드로 가는 길이있다고.. 이전 1 2 3 다음
