앳코더 ABC 456 후기
tkd0711 · 2026. 5. 2.
AtCoder Beginner Contest 456
https://atcoder.jp/contests/abc456
- 날짜: 2026-05-02 (Sat)
- 결과: A~D AC, E 도전
- B: 1틀
- C: 1틀
- D: 비교적 빠르게 해결
- E: 끝까지 고민해봄
1. 전체 느낌
이번 대회는 전체적으로 나쁘지 않았다.
A부터 D까지는 결국 다 풀었고,
E도 아예 손도 못 댄 게 아니라 끝까지 고민은 해봤다.
특히 이번 대회는
- B에서 단순한 구현 실수
- C에서 마지막 나머지 연산 실수
- D는 구조가 빨리 보였음
- E는 방향은 있었지만 끝까지 확신은 못 잡음
이런 식으로 정리할 수 있을 것 같다.
완벽한 대회는 아니었지만,
그래도 D까지 깔끔하게 마무리했고, E도 그냥 넘기지 않고 끝까지 붙잡아본 점은 괜찮았다.
2. A – 무난한 시작
A는 큰 문제 없이 넘어갔다.
요즘처럼 A는 초반 흐름을 잡는 문제라는 느낌이고,
이번에도 스타트 자체는 나쁘지 않았다.
3. B – 풀이 방향은 맞았는데, 단순한 인덱스 실수로 한 번 틀림
문제 요약
주사위 3개를 동시에 굴렸을 때,
나온 값이 4, 5, 6이 정확히 한 번씩 나올 확률을 구하는 문제였다.
접근
처음에는 각 주사위에서
- 4가 몇 면 있는지
- 5가 몇 면 있는지
- 6이 몇 면 있는지
를 세고,(4,5,6)의 순서를 바꾼 6가지 경우를 전부 더하면 되겠다고 생각했다.
이 발상 자체는 맞았다.
왜 처음 틀렸는가
문제는 구현에서 있었다.
처음 코드에서는 세 주사위 값을 꺼낼 때
- 첫 번째 주사위
- 두 번째 주사위
- 세 번째 주사위
를 써야 하는데,
실수로 전부 첫 번째 주사위에서만 값을 꺼내고 있었다.
즉, 아이디어가 틀린 게 아니라
그냥 인덱스를 잘못 쓴 단순한 구현 실수였다.
느낀 점
이런 문제는 더 아쉽다.
풀이 방향은 맞았는데
배열 인덱스 하나 잘못 써서 틀리면 체감상 더 허무하다.
작은 문제일수록
오히려 “입력을 내가 제대로 읽고 있나?”를 더 조심해야겠다는 생각이 들었다.
4. C – 거의 다 맞았는데 마지막 mod 한 번을 빼먹음
문제 요약
문자열의 부분문자열 중에서
서로 이웃한 두 문자가 같은 경우가 없는 것의 개수를 구하는 문제였다.
정답은 998244353으로 나눈 나머지를 출력해야 했다.
접근
이 문제는 비교적 바로 보였다.
현재 위치에서 끝나는 좋은 부분문자열 개수를 plus라고 두고,
- 이전 문자와 다르면
plus++ - 이전 문자와 같으면
plus=1
이렇게 관리하면
각 위치에서 끝나는 경우의 수를 차례로 더할 수 있었다.
즉, 연속해서 다른 문자가 이어지는 길이를 세면서 누적하는 문제였다.
왜 처음 틀렸는가
처음 제출한 코드는 거의 맞았는데,
마지막에 전체 답을 mod로 한 번 더 줄이는 부분을 빼먹었다.
중간 계산에서 나머지 연산을 하고 있었더라도,
최종 출력값도 반드시 mod를 적용해야 했다.
느낀 점
이건 알고리즘 실수라기보다
마무리 점검 실수였다.
나머지 연산 문제에서는 항상
- 중간값에 mod 했는지
- 마지막 출력도 mod 했는지
이 두 개를 같이 확인해야 한다는 걸 다시 느꼈다.
5. D – 상태를 바로 잡아서 비교적 빠르게 해결
문제 요약
문자열의 부분수열 중에서
서로 이웃한 두 문자가 같은 경우가 없는 것의 개수를 구하는 문제였다.
역시 998244353으로 나눈 나머지를 출력해야 했다.
접근
C가 부분문자열이었다면,
D는 부분수열이라 접근이 달랐다.
여기서는 상태를
- 현재 위치
idx - 직전에 선택한 문자
prv
로 두고,
- 현재 문자를 선택하는 경우
- 선택하지 않는 경우
로 나누면 되겠다고 바로 생각했다.
즉, 탑다운 메모이제이션으로
- 현재 문자가 이전 문자와 다르면 선택 가능
- 선택하지 않는 경우는 언제나 가능
이런 식으로 정리했다.
느낀 점
D는 문제를 보자마자 구조가 비교적 빨리 보인 편이었다.
현재 위치와 직전 문자 상태를 두는 방식이 바로 떠올랐고,
그 뒤에는 선택/비선택으로 무난하게 밀고 갈 수 있었다.
이번 대회에서 가장 편하게 풀린 문제는 D였던 것 같다.
6. E – 확신 있는 정답 구조까지는 못 갔지만, 끝까지 도전은 해봤다
문제 요약
도시마다 요일별 휴일 정보가 있고,
밤마다 이동하거나 머물면서
매일 정오에 있는 도시가 항상 휴일이 되도록 무한히 계속할 수 있는지 판별하는 문제였다.
요일 수 W는 최대 10이었다.
내가 본 방향
문제를 보면서
요일 수가 작으니까 상태를
- 현재 도시
- 현재 요일
정도로 두고 볼 수 있겠다고 생각했다.
즉 도시만 보는 게 아니라(도시, 요일) 상태 그래프로 보려는 방향까지는 갔다.
왜 끝까지 확신을 못 잡았는가
문제는
무한히 계속 가능하다는 조건을 내가 완전히 짧고 확실하게 정리하지 못했다는 점이었다.
처음에는 시작 도시에서 한 바퀴 돌아서
다시 시작점으로 올 수 있는지 같은 식으로 생각했는데,
나중에 보니 핵심은 그게 아니라
상태 그래프 전체에 순환이 존재하는지를 보는 문제였다.
즉 방향은 어느 정도 맞았지만,
조건을 정확하게 끝까지 정리하지 못해서 확신 있는 정답으로 못 밀어붙였다.
그래도 의미 있었던 점
그래도 이번 E는
완전히 감도 못 잡은 문제는 아니었다.
- 도시만 보면 안 되고
- 요일까지 포함한 상태를 봐야 하고
- 결국 그래프의 순환 여부를 보는 문제라는 방향까지는 갔다
이런 점에서
다음에 비슷한 문제가 나오면 훨씬 빨리 접근할 수 있을 것 같다.
즉 이번 E는 못 풀긴 했지만,
그냥 손도 못 댄 문제와는 좀 달랐다.
7. 이번 대회에서 좋았던 점
1) B, C에서 틀렸지만 빠르게 복구했다
둘 다 큰 발상 실수는 아니었고,
구현/마무리 실수를 바로 잡았다.
2) D는 구조를 빨리 봤다
현재 위치와 이전 문자 상태를 두는 방식이 비교적 자연스럽게 떠올랐다.
3) E도 끝까지 붙잡아봤다
맞추진 못했지만, 상태 그래프 방향까지는 생각해봤다는 점에서 의미가 있었다.
8. 아쉬웠던 점
1) B는 너무 단순한 구현 실수였다
아이디어보다 구현에서 틀린 문제라 더 아쉽다.
2) C는 마지막 mod 한 번을 빼먹었다
이런 마무리 실수는 진짜 줄여야 한다.
3) E는 방향은 있었는데 끝까지 확신을 못 만들었다
이런 문제를 나중에는 더 짧고 명확하게 정리할 수 있어야 할 것 같다.
사이클 탐지 , SCC 키워드를 얻어갔다
9. 다음 목표
- 작은 문제일수록 구현 실수 줄이기
- mod 문제에서는 마지막 출력까지 꼭 확인하기
- 상태 그래프 문제에서
“무한히 가능”이 결국 무엇을 뜻하는지 더 정확히 정리하기 - 못 푼 문제라도
방향까지는 잡아보는 연습 계속하기
한 줄 정리
ABC 456은 B와 C에서 구현 실수가 있었지만 빠르게 복구했고,
D는 구조를 잘 봤고, E도 맞추진 못했지만 끝까지 방향을 고민해본 대회였다.