반응형 Problem Solving242 백준 15685번 드래곤 커브 - C++ 풀이 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 드래곤 커브는 이루는 점들을 생성된 순서로 배열에 담는 것으로 나타낼 수 있다. 다음 세대 드래곤 커브는 현재 세대의 끝점(가장 최근에 생성된 점)을 기준으로 90도 회전하므로, 배열 역순으로 점들을 회전시켜준다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1의 방법으로 주어지는 드래곤 커브들을 모두 시뮬레이션으로 생성한 뒤, 드래곤 커브에 속하는 좌표를 체크해 조건.. 2022. 8. 14. 백준 1939번 중량제한 - C++ 풀이 1. 가중치 내림차순으로 간선을 정렬한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 1. 가중치 내림차순으로 간선을 정렬한다. 시작 공장에서 도착 공장으로 가는 경로에서 가중치가 가장 작은 간선이 한 번에 옮길 수 있는 중량의 최댓값을 결정한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 따라서 시작 공장에서 도착 공장으로 가는 경로가 생성될 때까지 가중치가 큰 간선부터 차례로 추가해보면 된다. 가중치가 큰 순서로 추가했으므로, 최초로 경로가 만들어지는 순간에 추가한 간선이 경로 내에서 최소 가중치를 갖는 간선이 되므로 해당 간선의 가중치가 답이 된다. #include #include using namespace std; typedef pair pii; typedef pair .. 2022. 8. 12. 백준 1699번 제곱수의 합 - C++ 풀이 1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수 2. dp(n) = min(1 + dp(n-i*i)) 1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수 dp(n)을 위와 같이 정의하자. 2. dp(n) = min(1 + dp(n-i*i)) n을 표현하는 제곱수 중 하나로 i*i를 골랐다고 가정하자. 이제 (n - i*i)를 제곱수들의 합으로 표현해야 하므로, dp(n) = 1 + dp(n-i*i)가 된다. 따라서 i*i가 n 이하인 모든 i에 대해 dp(n) = 1 + dp(n-i*i)값을 계산하고, 그중 최솟값을 찾으면 된다. 기저 사례는 n이 1 이하일 때, dp(0) = 0, dp(1) = 1. #include #include using names.. 2022. 8. 12. 백준 2307번 도로검문 - C++ 풀이 1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다. 2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다. 1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다. 먼저 검문을 하지 않았을 때 최단 시간을 알아야 지연 시간을 계산할 수 있다. 다익스트라 알고리즘을 사용해서 최단 시간을 구한다. 이때 최단 경로도 함께 구해둔다. 최단 경로에 포함되지 않은 도로를 검문해봤자 용의자가 최단 경로로 이동하면 지연시간이 0이기 때문에, 지연 시간을 최대로 하기 위해서는 최단 경로에 포함된 도로에서 검문을 해야 하기 때문이다. 2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다. 간선을 하나 지웠을 때 용의자의 최단 이동 시간도 다익스트라를.. 2022. 8. 10. 백준 2668번 숫자고르기 - C++ 풀이 1. 첫째 줄에서 둘째 줄로 가는 간선을 추가한다. 2. 완성된 그래프에서 사이클에 속하는 숫자들을 선택한다. 1. 첫째 줄에서 둘째 줄로 가는 간선을 추가한다. 문제에 주어진 예시 상황에서 첫째 줄의 1을 선택했다고 가정하자. 이에 대응하는 둘째 줄 숫자는 3이므로 첫째줄에서도 3을 추가해야 한다. 따라서 첫째 줄의 3을 고르고 나면, 또 첫째 줄 3에 대응하는 둘째 줄 숫자는 1이므로 첫째줄에서 1을 골라야 한다. 이러한 흐름을 그래프로 나타낼 수 있다. 각 숫자를 정점이라고 생각하고, 첫째 줄에서 둘째 줄로 가는 간선을 추가하여 두 집합이 일치하기 위해 추가해야 하는 수의 흐름을 나타낸다. 문제에서 주어진 예시 상황의 경우 1 -> 3, 2 -> 1, 3 -> 1,... 을 추가하면 된다. 2. 완.. 2022. 8. 9. 이전 1 ··· 10 11 12 13 14 15 16 ··· 49 다음 반응형
