본문 바로가기
반응형

Problem Solving/BOJ228

백준 13913번 숨바꼭질 4 - C++ 풀이 1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 2. BFS 과정에서 이전 노드를 기록하여 경로를 구할 수 있도록 한다. 1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 수 하나를 노드 하나라고 생각하고, n번 노드와 [n+1, n-1, 2n]번 노드는 간선으로 이어져있다고 생각하면 된다. BFS를 이용하여 N번 노드에서 K번 노드까지의 거리를 구한다. 이때 노드 번호의 범위를 [0, 200000]으로 제한할 수 있다. N, K의 범위가 100,000이므로 거리의 최댓값은 100,000이다. 그런데 200,000보다 큰 노드의 경우 더 작아지는 방법은 -1 밖에 없기 때문에 최소 100,000번의 연산을 해야 K로 갈 수 있다. 따라서 200,000을 넘어가는 수는 고려하지 .. 2022. 8. 17.
백준 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.
반응형

티스토리툴바