문제 백준 1354번 풀이 문제는 $ A_{n} $을 구하는 것입니다. $ A_{i} $에 대한 점화식이 문제에 나와 있으니 재귀적으로 풀어봅시다. 피보나치 수열과 마찬가지로 비슷한 값의 중복 연산을 피하기 위해 DP를 사용해야 합니다. 이 문제의 경우 항 $ i $가 불연속적이고 매우 크므로, map을 사용해야 메모리 초과를 피할 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; unordered_map mp; ll n, p, q, x, y; ull ..

문제 백준 16172번 풀이 번형된 문자열 $ S $를 입력 받고 0-9를 모두 제거합니다. 찾고자 하는 문자열 $ T $를 전처리한 문자열 $ S $에서 선형 탐색($ O(|S|) $)하여 찾아줍니다. 선형 탐색을 굳이 구현할 필요 없이 STL에서 stirng.find를 지원해주니 find의 반환값이 string::npos인지 확인만 해주면 됩니다. 다만 주의할 점은 $ S $에서 0-9를 제거할 때, $ S.erase $를 사용하면 최악의 경우 $ O(|S|^2) $으로 TLE가 날 수 있습니다. 이 때문에, 다른 변수를 만들어 전처리해야 합니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ul..

문제 백준 1445번 풀이 우선 순위를 "쓰레기로 차있는 칸을 적게 지나가는 것"(A)을 높게 주고, "인접한 면을 적게 지나가는 것"(B)을 낮게 줍시다. 데이터를 두개로 관리하면서 다익스트라를 돌려주면 풀 수 있습니다. 그런데, 재미있는 풀이가 있어서 다뤄보려고 합니다. 위에서 우선 순위를 A를 높게, B를 낮게 줬고, A의 경우에 드는 가중치(비용)을 $ cost(A) $, B를 $ cost(B) $라고 둡시다. 각 정점까지 오는데의 비용을 아무리 $ cost(B) $를 합해도 $ cost(A) $가 안되도록 $ cost(A) $의 값을 설정합시다. 이 문제에서 정점의 개수가 많아봐야 2500개이므로, $ cost(B) = 1$, $ cost(A) = 2500 $으로 둡시다. 인접한 면을 지날 때는..

문제 백준 1595번 풀이 임의의 정점 $ v_{0} $에서 가장 먼 정점 $ v_{1} $을 DFS 또는 BFS로 찾아줍니다. 다시 정점 $ v_{1} $에서 가장 먼 정점 $ v_{2} $를 찾아줍니다. 도시 $ v_{1} $과 $ v_{2} $의 거리가 정답이 됩니다. 자료형에 유의해줘야하는데, int를 사용하면 12%에서, long long을 사용하면 100%에서 틀렸습니다. unsigned long long 박으니 풀렸습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef pair pull; typedef ..

문제 BOJ 1484 풀이 문제에서 주어진 조건대로 식을 세워봅시다. 성원이가 기억하고 있는 몸무게를 $ M $, 현재 몸무게를 $ x $로 둡시다. $$ x^2 - M^2 = G $$ $$ (x - M)(x + M) = G $$ $ a = x - M, b = x + M $이라고 둡시다. (단, $ a $, $b $는 정수) $ a \cdot b $이 $ G $가 되려면, $ a $와 $ b $가 $ G $의 약수가 되면 됩니다. $ a $와 $ b $를 알고 있으니 연립 일차 방정식을 사용하여 $ x $를 구할 수 있습니다. $$ x = \frac{a + b}{2} $$ 자연수라는 조건을 충족하려면, $ a + b $가 짝수가 되면 됩니다. 엣지 케이스를 생각해봅시다. 약수 $ a $와 $ b $가 같..

문제 BOJ 1253 풀이 $ i $번째 수를 만들기 위해 $ j $번째 수와 $ k $번째수를 구한다고 가정합시다. 순서쌍 $ (i, j) $를 모두 구하면 경우의 수가 $ {n}C_{r} $이 됩니다. 이 순서쌍에서 남은 $ k = (i - j) $를 이분 탐색을 사용하여 log 복잡도로 구해봅시다. 그리고, 이분 탐색을 사용하여 구한 $ k $가 $ i $ 혹은 $ j $와 겹치는 경우를 확인하여 추가로 탐색해야 합니다. 전체 시간복잡도가 $ O(N^2logN) $이 되므로 시간 내에 해결할 수 있습니다. 이 문제에서 유의해야할 점은 $ A_{i} $와 $ A_{j} $가 같더라도 서로 다른 수로 취급합니다. 문제의 질문에서 여러 테스트 케이스를 정리해두었으니 직접 푸는데 도움이 되길 바랍니다. 6..