문제해결
-
백준 1260번: DFS와 BFS문제해결 2023. 11. 30. 16:27
DFS와 BFS 너무 정직한 DFS, BFS 문제이다. 다만,단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,이 부분 참고하여, DFS, BFS할 때 FIFO, LIFO에 맞춰 저렇게 sort 해준 뒤 push_back 해주면 끝. #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int N, M, V; vector av[1000]; bool visited[1000]; void dfs() { memset(visited, 0, sizeof(bool) * 1000);..
-
백준 1629번: 곱셈문제해결 2023. 11. 28. 21:05
곱셈 행렬곱셈 문제 풀며 썼던 분할정복. 처음엔 홀수일 때long long int ret = (a * ab_2 * ab_2) % C;이런식으로 했더니 계속 오버플로우가 났고 나는 그냥 어리둥절하고만 있었다.long long int ret = (a * ((ab_2 * ab_2) % C) % C;사실상 이렇게 했어야 했는데, 아무래도 코드를 잘 정리해 두어야 하는 이유가 아닌가 싶다. #include using namespace std; #define ll long long int ll A, B, C; ll times(ll a, ll b) { if (b == 1) return a % C; ll ab_2 = times(a, b / 2) % C; ll ret = (ab_2 * ab_2) % C; if (b & ..
-
백준 11687번: 팩토리얼 0의 개수문제해결 2023. 11. 28. 18:16
팩토리얼 0의 개수 그냥 무작정 1부터 M까지 계수를 셌다. 당연히 시간초과가 뜰거라 생각했는데 AC되었다. M이 1억일 경우 100'000'000번 넘게 연산이 되는데 어떻게 0.5초만에 된거지 #include using namespace std; int M; int get_5(int f) { int fives = 0; while (!(f % 5)) { f /= 5; fives += 1; } return fives; } int main() { cin >> M; long long f = 0, val = 0; while (true) { f += 5; val += get_5(f); if (val == M) { cout
-
백준 23253번: 자료구조는 정말 최고야문제해결 2023. 11. 28. 16:56
자료구조는 정말 최고야 스텍들 돌아가며 하나씩 팝 하면 되는 간단한 실버5 자료구조 문제인줄 알았다. 제출하고보니 계속 시간초과가 뜨길래 뭔가 이상함을 느꼈다. 생각해보니 200'000개의 책을 하나씩 200'000개의 더미로 놓은 다음, 200'000 199'999 ... 2 1 이런식으로 배치하면 총 20'000'100'000번 순회해야하니 당연히 시간초과가 날 수밖에 없다. 문제를 다시 읽어보니, 스택이 내림차순인지 확인을 하기만 하면 될 듯 하여 다시 제출하고 AC되었다. #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) f..
-
백준 9251번: LCS, 백준 5582번: 공통 부분 문자열문제해결 2023. 11. 20. 19:57
LCS, 공통 부분 문자열 dp는 할때마다 어려운 것 같다. O(N) dp에 좀 적응했다 싶었는데 O(N²) dp가 나와서 애먹었는데, 이번엔 2차원 dp다.이런식으로 dp를 진행하면 된다. // 9251번: LCS #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i > s1 >> s2; if (s2.length() > s1.length()) swap(s1, s2); FOR(i, s1.length()) { i..
-
백준 9935번: 문자열 폭발문제해결 2023. 11. 20. 15:58
문자열 폭발 int pos = str.find(bomb); while (pos != string::npos) { str.erase(str.begin() + pos, str.begin() + pos + bomb.size()); pos = str.find(bomb); }혹시나 싶어 이런식으로 날먹을 시도해봤는데, 역시 안되더라 #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i > str >> bomb; FORL(e, str..
-
백준 11689번: GCD(n, k) = 1문제해결 2023. 11. 20. 14:44
GCD(n, k) = 1 1'000'000까지의 소수를 모두 만들고, 소인수분해 한 후 오일러 곱 공식을 이용해서 풀려고 했다. 하지만 반례를 못찾아서 계속 끙끙대다 결국 답지를 열어버렸다. 반례는, 소인수분해를 했을 때, 소인수가 p, q, r, s일 경우 $ans = n\times \left ( 1-\frac{1}{p} \right )\times \left ( 1-\frac{1}{q} \right )\times \left ( 1-\frac{1}{r} \right )\times \left ( 1-\frac{1}{s} \right )$ 이 답이 되는데, s가 만약 1'000'000보다 큰 수라면, 해당 연산에 포함되지 못해 생기는 문제였다. 남은 s를 소인수에 추가해서 해결했다. 저번에도 정확히 같은 문..