앳코더 ABC 446 후기
tkd0711 · 2026. 2. 21.
AtCoder Beginner Contest 446
https://atcoder.jp/contests/abc446
- 결과: A~D AC (1000점)
- D – Max Straight: 4트 AC
1. 전체 흐름
A, B는 무난하게 처리.
C도 크게 막히지 않고 해결.
문제는 D였다.
최종적으로는 AC했지만,
접근을 잘못 잡아서 60분 가까이 소비했다.
2. D – Max Straight
문제 요약
- 수열 A
- B는 subsequence
- 조건:
B_i + 1 = B_{i+1} - 최대 길이 구하기
3. 삽질 타임라인
1️⃣ 21:29 – LIS 착각 (WA)
문제를 대충 읽고
“subsequence + 증가”라고 생각해서
그냥 LIS로 접근했다.
하지만 조건은:
증가가 아니라 정확히 +1
여기서 이미 방향이 틀어졌다.
2️⃣ 21:59 – 2차원 DP (RE, 메모리 폭발)
값 범위가 1e9라 배열 dp를 못 쓰겠다고 생각하고(idx, prvidx) 상태의 2차원 완탐 DP를 구현.
N ≤ 2×10^5인데int[n][n] → 즉시 메모리 폭발 (약 900MB 사용)
여기서 문제를 인덱스 기준으로 본 것이 실수였다.
3️⃣ 22:08 – 이분탐색 + 완탐 (TLE)
길이에 대해 이분탐색하고can(v)를 완전탐색으로 구현.
시간초과 날 걸 알면서도 일단 제출.
N=2e5에서 O(N² log N)은
애초에 불가능한 구조였다.
4️⃣ 22:30 – 정답 (HashMap DP)
담배 피면서 다시 생각.
이 문제는:
- “이전 인덱스”가 중요한 게 아니라
- “이전 값(a-1)”이 중요하다는 걸 깨달음
최종 풀이:
HashMap<Integer,Integer> map = new HashMap<>();
int max = 0;
for(int i = 0; i < n; i++){
int cur = arr[i];
int best = Math.max(map.getOrDefault(cur, 0),
map.getOrDefault(cur-1, 0) + 1);
map.put(cur, best);
max = Math.max(max, best);
}값 기반 DP로 해결.
4. 왜 아쉬웠는가
이 문제는 사실 구조가 단순했다.
- 정확히 +1 조건
- 값 기반 연결
- O(N) HashMap DP
처음에 조건을 정확히 읽고
“이건 LIS가 아니라 값 연결이네”만 했어도
20분 안에 풀 수 있었을 문제였다.
초반 10분을 템플릿으로 날린 게
오늘 가장 아쉬운 부분.
5. 한 줄 정리
오늘은 실력이 부족한 날이 아니라,
문제를 너무 빨리 결론 내린 날이었다.
솔직히 말하면,
점수는 1000점이지만 체감은 아쉬운 날이다.
그래도 D를 결국 스스로 구조 전환해서 풀어낸 건
분명 성장이다.