반응형 수학14 프로그래머스 당구 연습 - C++ 풀이 1. 4개의 벽면을 맞추는 경우를 모두 탐색하고 최소거리를 구한다. 2. 만약 벽면에 맞기 전에 공을 먼저 맞는 경우 원쿠션이 되지 않으므로 제외한다. 1. 4개의 벽면을 맞추는 경우를 모두 탐색하고 최소거리를 구한다. 벽면이 총 4개 있으므로, 각 벽면을 맞추는 경우를 모두 탐색한 다음 최소거리를 구하면 된다. 벽면을 맞추고 공을 맞추기 위해 이동해야 하는 거리는 해당 벽면을 기준으로 목표공을 대칭이동 시킨 뒤 시작점과의 거리를 계산하면 된다. 2. 만약 벽면에 맞기 전에 공을 먼저 맞는 경우 원쿠션이 되지 않으므로 제외한다. 주의해야 하는 부분은 벽면을 맞추고 난 뒤에 목표공을 맞추는 것이 불가능할 수 있다는 점이다. 벽면으로 가는 경로에 목표공이 존재하는 경우에 해당한다. #include #incl.. 2023. 9. 5. 프로그래머스 두 원 사이의 정수 쌍 - C++ 풀이 1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다. 2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다. 3. | k | ≥ r1이면 2 * (floor(hi) + 1)개이다. 1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다. x 좌표를 기준으로 -r2부터 r2까지 탐색하며 주어진 조건을 만족하는 점들의 개수를 구해나가자. 2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다. 두 원 사이의 공간에 위치한 점.. 2023. 9. 5. 백준 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. 백준 14476번 최대공약수 하나 빼기 - C++ 풀이 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다. 3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다. 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 어떤 수를 제외한 나머지 수들의 gcd를 O(1)에 구하기 위해 누적 gcd 배열을 활용할 것이다. A[0]~A[i] 까지의 최대 공약수는 prefixGCD[i], A[i]~A[N-1]까지의 최대공약수는 suffixGCD[i]라고 할 때, prefix GCD 배열과 suffix GCD 배열을 구해준다. 이 과정의 시간 복잡도는 O(N) 2. i번째 .. 2022. 6. 13. 백준 2981번 검문 - C++ 풀이 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 3. A[i+1] - A[i](0 ≤ i < N-1)의 최대 공약수의 약수들이 가능한 모든 M이 된다. 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 두 수 a, b를 M으로 나눈 나머지가 r로 같다면, 두 수 a, b는 아래와 같이 나타낼 수 있다. a = M*(a/M) + r b = M*(b/M) + r 위 식에서 아래를 빼면 a-b = M*(a/M-b/M)이므로 (a-b)는 M으로 나누어 떨어진다. 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 또한 두 수 a, b를 M.. 2022. 6. 9. 이전 1 2 3 다음 반응형
