앳코더 ABC 452 후기
tkd0711 · 2026. 4. 4.
AtCoder Beginner Contest 452
https://atcoder.jp/contests/abc452
- 날짜: 2026-04-04 (Sat)
- 결과: A~C AC, D 미해결
- A: 1분대 AC
- B: 4분대 AC
- C: 23분대 AC
- D: 미해결
1. 전체 느낌
이번 대회는 결과만 보면 A~C까지 풀고 600점이었다.
A, B는 비교적 빠르게 마무리했고,
C도 나쁘지 않은 시간 안에 원트로 해결했다.
문제는 D였는데, 거의 1시간 20분을 붙잡고도 끝내지 못했다.
이번 대회는 C까지는 흐름이 괜찮았는데,
D에서 문제를 끝까지 정리하지 못하면서 체감이 많이 안 좋았다.
즉 이번 대회는
- 초반 운영은 괜찮았고
- C까지도 나쁘지 않았지만
- D 한 문제에서 사고가 꼬이면서 멈춘 대회
라고 보는 게 맞다.
2. A, B – 비교적 깔끔한 출발
A는 2분 안쪽으로 해결했고,
B도 크게 흔들리지 않고 처리했다.
최근처럼 A, B는 어느 정도 안정권에 들어온 느낌이다.
예전처럼 초반부터 리듬이 무너지지는 않았고,
이번에도 C에 들어가기 전까지 흐름은 괜찮았다.
3. C – Fishbones: 조건을 잘 단순화해서 해결
문제 요약
척추에 길이 N짜리 문자열 하나를 쓰고,
각 갈비뼈 i에는 길이 A_i인 문자열을 쓰는데,
그 문자열의 B_i번째 문자가 척추 문자열의 i번째 문자와 같아야 한다.
사용할 수 있는 문자열 후보는 S_1 ... S_M이고,
각 후보 S_j가 척추 문자열로 가능하면 Yes, 아니면 No를 출력하는 문제였다.
접근
핵심은 각 갈비뼈가 서로 독립적이라는 점이었다.
어떤 척추 문자열이 가능하려면,
척추의 각 위치 i에 대해
“길이 A_i인 문자열들 중 B_i번째 문자가 무엇이 될 수 있는가”만 알면 된다.
그래서:
- 각 갈비뼈 위치마다 가능한 문자 집합을 만든다.
- 각 문자열
S_j가 길이N인지 확인한다. - 길이가 맞다면 각 위치 문자가 그 집합에 포함되는지 검사한다.
이 방식으로 풀었다.
왜 되는가
중요한 건 문자열 중복 사용이 가능하다는 점이다.
즉 갈비뼈 1에 어떤 문자열을 썼는지와
갈비뼈 2에 어떤 문자열을 썼는지가 서로 충돌하지 않는다.
그래서 백트래킹이나 매칭처럼 복잡하게 볼 필요가 없고,
각 위치별로 가능한 문자만 미리 모아두면 된다.
시간복잡도
N ≤ 10M ≤ 200000- 문자열 길이도 최대 10
이라서
- 각 위치마다 모든 문자열을 한 번씩 보는 것
- 그 뒤 각 후보 문자열을 검사하는 것
모두 합쳐도 O(NM) 수준이라 충분히 가능했다.
느낀 점
C는 “대충 한 것 같다”는 느낌이 들 수 있는데,
사실은 조건을 꽤 정확하게 잘 단순화한 문제였다.
괜히 더 어렵게 생각하지 않고,
“각 위치별 가능한 문자 집합만 만들면 된다”는 구조를 잘 잡은 편이었다.
4. D – No-Subsequence Substring: 최소 끝점 하나를 못 잡아서 꼬임
문제 요약
문자열 S의 부분문자열들 중에서,
문자열 T를 부분수열로 포함하지 않는 것의 개수를 세는 문제였다.
즉:
- 부분문자열은 연속이어야 하고
- 부분수열은 연속일 필요는 없다
이 차이를 잘 다뤄야 하는 문제였다.
처음 막힌 이유
문제 자체를 처음 읽었을 때부터 조금 헷갈렸다.
S의 부분문자열을 잡고- 그 안에서
T가 부분수열이 되는지 본다
라는 구조인데,
처음엔 가능한 경우를 전부 세려고 하다 보니 사고가 많이 복잡해졌다.
특히 abrakadabra, T = aba 같은 예시를 가지고 손으로 세다가,
어느 순간부터 “가능한 subsequence 조합 개수”를 세는 쪽으로 생각이 꼬였다.
실제 핵심
이 문제의 핵심은 조합 수를 세는 게 아니었다.
시작점 l을 하나 고정했을 때,
그 시작점에서 T를 부분수열로 처음 만들 수 있는 가장 빠른 끝점 rmin 만 알면 된다.
그 이유는:
S[l..rmin]이 이미T를 부분수열로 포함하면- 그보다 더 긴
S[l..r]도 전부T를 포함하게 되기 때문이다.
즉 시작점 l에서 나쁜 부분문자열 개수는
“가능한 subsequence 경우의 수”가 아니라
rmin부터 끝까지의 개수
딱 이거 하나였다.
내가 꼬인 지점
중간에 개수를 손으로 세면서
“19개인가?”, “15개가 넘나?” 이런 식으로 생각이 섞였던 부분이 있었는데,
그게 정확히 꼬인 지점이었다.
이 문제는
- 가능한
(a,b,a)조합 개수를 세는 문제도 아니고 - subsequence가 되는 모든 방법 수를 세는 문제도 아니다.
그냥
시작점마다
T를 처음 만들 수 있는 최소 끝점 하나
만 찾으면 되는 문제였는데,
그걸 조합 개수 문제처럼 바라보다가 사고가 복잡해졌다.
정답 구조
정답은 보통 이렇게 간다.
- 전체 부분문자열 개수 =
N*(N+1)/2 T를 부분수열로 포함하는 “나쁜” 부분문자열 개수를 센다.- 답 = 전체 - 나쁜 것
그리고 나쁜 부분문자열 개수는
각 시작점 l마다 T를 가장 빨리 완성하는 끝점 rmin을 찾고,
그 뒤 끝점들은 모두 나쁘다고 보고 더하면 된다.
왜 더 아쉬운가
이 문제는 “전혀 감이 없던 문제”는 아니었다.
중간에 네 메모에서도
“현재 부분수열이 T가 되면 그 뒤는 전부다 안 되는 거니까 그런식으로 가야하나?”
라고 적은 부분이 있었는데,
그 감각 자체는 정답에 굉장히 가까웠다.
즉 방향은 거의 근처까지 갔는데,
끝까지 “최소 끝점 하나만 찾으면 된다”로 정리하지 못한 게 아쉬운 문제였다.
5. 이번 대회에서 좋았던 점
1) A, B가 안정적이었다
초반 문제에서 크게 흔들리지 않았다.
2) C를 정확하게 단순화했다
조건이 꽤 많아 보였지만,
실제로 필요한 정보만 뽑아서 깔끔하게 해결했다.
3) D에서도 정답 방향 근처까지는 갔다
완전히 엉뚱한 길을 간 건 아니었고,
핵심 감각은 어느 정도 잡고 있었다.
6. 아쉬웠던 점
가장 큰 아쉬움은 역시 D였다.
- 조합 수를 세려는 쪽으로 생각이 샜고
- 시작점별 최소 끝점 하나만 보면 된다는 걸 끝까지 정리하지 못했다.
즉 이번 D는 알고리즘을 아예 몰랐다기보다,
문제를 끝까지 단순한 구조로 정리하지 못해서 멈춘 문제
였다.
이건 실력 부족과는 조금 다르다.
핵심은 보였는데,
그걸 짧고 단순한 식으로 끝까지 가져가지 못한 것이다.
7. 다음 목표
- 부분문자열/부분수열 문제가 나오면
“직접 세는 게 아니라 반대로 셀 수 있는가” 먼저 생각하기 - 시작점을 고정했을 때
“최소 끝점 하나만 찾으면 되는 구조”인지 의심하기 - 조합 수를 세는 문제인지,
경계점 하나를 찾는 문제인지 빨리 구분하기 - 감은 잡았는데 복잡해질 때
더 많은 경우를 세기보다 “진짜 필요한 정보가 하나인지” 다시 보기
한 줄 정리
ABC 452는 C까지는 흐름이 괜찮았지만, D에서 “가능한 방법 수”를 세는 쪽으로 사고가 꼬이면서 멈춘 대회였다.