본문 바로가기
반응형

Problem Solving242

백준 17135번 캐슬 디펜스 - C++ 풀이 1. 먼저 궁수 3명의 타깃을 계산만 한 뒤, 모아서 한 번에 죽인다. 2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.) 3. 1, 2번 과정을 N-1번 반복한다. 1. 먼저 궁수 3명의 타겟을 계산만 한 뒤, 모아서 한 번에 죽인다. 궁수끼리 적이 중복될 수 있다. 따라서 타겟을 계산하고 바로 죽이면 안 되고, 궁수 3명의 타깃을 일단 계산만 한 뒤에 3개의 타깃을 한 번에 죽여야 한다. 타깃 계산은 거리가 가까운 순으로, 거리가 가깝다면 왼쪽에 있는 순으로 반복문을 이용해서 간단하게 구현하였다. 2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.) 모든 적을 한 칸 내린다. 대신 궁수를 한칸 올려도 똑같은 상황이기 때문에 아래 코드에서는 궁수를 올려주었다. 다만 궁.. 2022. 7. 24.
백준 11778번 피보나치 수와 최대공약수 - C++ 풀이 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 위와 같은 피보나치의 성질을 이용해서 푸는 문제였다. 증명은 여기를 참고했다. https://math.hmc.edu/funfacts/fibonacci-gcds-please/ 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 먼저 m과 n의 최대 공약수를 구해야 한다. 유클리드 호제법을 사용하여 O(logN)에 구해준다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 피보나치 수열을 행렬의 거듭제곱으로 나타낸 .. 2022. 7. 22.
백준 1561번 놀이 공원 - C++ 풀이 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 시간이 주어지면 해당 시간까지 각 놀이기구가 몇 번 운행되는지 구할 수 있다. 따라서 먼저 모든 사람이 놀이기구에 탑승하는 데 걸리는 시간 totalTime을 찾아주자. 파라매트릭 서치를 이용하여 O(log30N)에 totalTime을 구할 수 있다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 현재 시각을 t라고 하면, 마지막 놀이기구는 t = totalT.. 2022. 7. 21.
백준 1113번 수영장 만들기 - C++ 풀이 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 하늘에서 비를 내린다고 생각하자. 낮은 칸부터 점차 물이 차오를 것이다. 이것을 시뮬레이션해준다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 비가 내려도 담기지 않고 밖으로 흐르는 칸이 있을 수도 있다. 바깥 칸에서 시작해서 현재 높이 이하인 칸만 방문하는 DFS/BFS를 수행했을 때, 방문되는 칸이라면 밖으로 흐르는 칸이다. #include #include using namespace std; int N, M; int board[52][52].. 2022. 7. 20.
백준 2086번 피보나치 수의 합 - C++ 풀이 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 2. 점화식을 행렬 곱으로 나타낸다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 피보나치수열을 점화식으로 나타내면 f(n) = f(n-1) + f(n-2), f(1) ~ f(n)의 합을 g(n)이라고 하면, g(n) = g(n-1) + g(n-2) + 1이다. 2. 점화식을 행렬 곱으로 나타낸다. g에 대한 점화식을 다음과 같은 행렬 곱으로 나타낼 수 있다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 분할 정복을 이용하여 거듭제곱을 계산하여 시간 초과를 피한다. #.. 2022. 7. 19.
반응형

티스토리툴바