분명 처음에 접할 때는 단순한 BFS 문제로 생각해서 쉽다고 여겼으나, 역시나 또 다시 시간 초과를 맞닥뜨렸다. 아무래도 주어진 규칙에 내포된 패턴을 파악해야 하는데, 그렇지 못하고 계속 규칙만을 활용한 무식한 방법을 써서 그런 것 같다. 그래도 시간 초과를 방지하기 위해 만든 장치 1. 중복 탐색을 막기 위한 set 2. 목표로 하는 t 문자열과 다른 알파벳 구간부터 교체 (즉 ab에서 ba로, bc에서 cb로 바꿀 수 있어도 목표로하는 문자열과 동일하면 교체 X) 위 장치를 도입해도 시간 초과가 발생하였다. 아무리 생각해도 내 뇌 용량을 초과하는 문제인 것 같아서 대회 후 댓글을 결국 열어 보았다. 교체 패턴을 살펴보면, ab → ba, bc → cb 식으로만 가능하다. 이를 통해 아래와 같은 발견을..

https://codeforces.com/contest/1697/problem/B Problem - B - Codeforces codeforces.com 아쉽게도 시간 초과가 발생해서 틀린 문제이다. 시간 초과가 발생한 풀이법 i개의 아이템을 가격 내림차순으로 정렬한 후, $y$는 $x$개의 아이템들 중 가장 저렴한 아이템의 개수이므로 $p_1...p_x$ 총 $x$개 중에서 뒤에서부터 $y$개를 방문하며 합을 구하도록 하였다. 그런데 시간 초과가 발생하다 이번에는 x 구간 내에서 y 구간과 비 y 구간의 크기를 비교하여 크지 않은 곳의 합을 구하여 최종적으로 y구간의 합을 구하는 방법을 택했다. 그런데 이번에도 시간 초과 발생!!........ㅠㅠ 시간 초과가 발생하지 않은 방법 도저히 방법이 떠오르지..

💚 2003 수들의 합 2 총 방법의 수 3가지 - $O(N^3)$: i 정하기, j 정하기, i ~ j 구간합 구하기 - $O(N^2)$: i 정하기, j 정하기, 합은 중복 합 활용 - $O(N)$: 모든 배열값이 양수라는 점 활용 i = a, j = b의 합이 M보다 작았고 i = a, j = b + 1의 합이 M보다 큰 경우를 생각해보자. 식으로 나타내면 다음과 같다. $A[a] + A[a + 1] + ... + A[b] m$ 이 경우 j를 계속 증가시키는 것은 의미가 없기 때문에 i를 증가시켜야 한다. 그런데 i = a + 1, a + 1 $ M이기 때문에 처음의 전제와 다르고 모수닝 발생한다. 따라서 이런 경우는 i만 증..

💚 16988 Baaaaaaaaaduk2(Easy) 시간 복잡도는 크게 2부분을 나뉜다. 돌을 2개 놓는 부분 알아보기$(NM)^2$, 죽일 수 있는 상대 돌의 개수 세기 BFS →$(NM)$ 여기서 BFS를 할 때, 내 돌을 기준으로 BFS 탐색을 하는 것이 아니라 상대 돌을 기준으로 탐색한다는 점이 포인트이고, 만약 탐색 중 빈 공간을 만나면 dead로, 유효하지 않음을 처리하는 것도 중요하다. #include #include #include #include #include #include using namespace std; int n, m; int a[20][20]; bool check[20][20]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; i..

💚 17070 파이프 옮기기 1 파이프가 2개의 칸에 걸쳐있어도 알고리즘 풀이에는 파이프의 오른쪽 칸으로만 파악하면 된다. 방향이 제한되어있기 때문이다. 방법의 수가 $10^6$ 이하이므로 Brute Force 탐색이 가능하다. 조금 비효율적으로 반복되는 코드를 작성했더니 역시나 실수가 자주 발생해서 디버깅에 시간이 더 오래 걸렸다. #include #include // 10^6 이하이기 때문에 브루트 포스 가능 using namespace std; // 오른쪽, 아래, 오른쪽 아래 int dr[] = {0, 1, 1}; int dc[] = {1, 0, 1}; int n; bool inside(int r, int c) { return r >= 0 && r = 0 && c < n; } i..

💚 16968 차량 번호판 1 - 차량 번호판은 길이가 4이하이면서, c와 d로 이루어진 문자열 - c는 문자, d는 숫자 - 같은 문자나 숫자가 두 번 연속해서 나타나면 안된다. - 가능한 차량 번호판의 개수를 구하는 문제 - 전체 경우의 수를 살펴보는 것이 가능하다. - 조합을 해결해 풀 수도 있다.(난 처음에 바로 이걸 생각했다.) 예를 들어 cccc인 경우에는 $26 \times (26 - 1) \times (26 - 1) \times (26 - 1) \times (26 - 1) $ ccdd인 경우에는 $26 \times (26 - 1) \times 10 \times (10 -1)$ #include using namespace std; int go(string &s, int index, char ..