앳코더 ABC 459 후기
tkd0711 · 2026. 5. 23.
AtCoder Beginner Contest 459
https://atcoder.jp/contests/abc459
- 날짜: 2026-05-23 (Sat)
- 결과: A~D AC, 1000점
- 풀이 순서: A → B → D → C
- A: 1:41
- B: 15:28
- D: 45:18
- C: 91:01, 5틀
1. 전체 느낌
이번 대회는 여러모로 기억에 남을 것 같다.
일단 어제 취업했다.
그리고 그날 밤에 앳코더도 했다.
결과는 A~D AC, 1000점.
점수만 보면 나쁘지 않은데, 체감은 꽤 다산다난했다.
A, B를 풀고 D를 먼저 해결한 뒤,
마지막에 C로 돌아와서 오래 맞고 겨우 해결했다.
특히 C는 처음 보는 유형의 관리 문제라서 생각보다 많이 헤맸다.
그래도 끝까지 포기하지 않고 결국 AC까지 가져간 점은 좋았다.
오늘은 깔끔하게 푼 대회라기보다, 끝까지 물고 늘어져서 살아남은 대회였다.
2. A, B – 초반은 무난했지만 B에서 약간 아쉬움
A는 큰 문제 없이 해결했다.
B는 처음에 배열을 만들어서 일반적으로 처리하려고 했다.
그런데 경우가 4개짜리라서, 중간에 그냥 하드코딩으로 전환했다.
결과적으로 풀긴 했지만,
처음부터 “이 정도 경우의 수면 그냥 직접 처리하는 게 빠르다”고 판단했으면 조금 더 시간을 줄일 수 있었을 것 같다.
이번 B에서 느낀 점은 이거다.
작은 경우의 수 문제에서는 괜히 일반화하려다가 구현이 더 무거워질 수 있다.
제한이 작고 경우가 적으면, 빠르게 직접 처리하는 판단도 필요하다.
3. D – 생각보다 빠르게 푼 문제
D는 C보다 먼저 풀었다.
문제는 문자열을 재배열해서
인접한 두 문자가 같지 않게 만들 수 있는지 판별하고, 가능하면 실제 문자열을 출력하는 문제였다.
처음 봤을 때 느낌은 꽤 단순했다.
가장 많이 남은 문자를 우선적으로 배치하되,
직전에 쓴 문자와는 다른 문자를 고르면 되지 않을까?
그래서 각 문자 개수를 세고,
매번 직전 문자와 다른 것 중 남은 개수가 가장 많은 문자를 골랐다.
알파벳은 26개뿐이고,
모든 테스트 케이스 문자열 길이 합도 제한이 있어서
매번 26개를 훑는 방식으로 충분했다.
이 문제는 “한 문자가 너무 많으면 불가능하다”는 감각도 있었고,
구현도 크게 꼬이지 않았다.
오늘 D는 꽤 잘한 편이었다.
C에서 오래 고생한 것과 다르게, D는 구조가 빨리 보였다.
4. C – 오늘의 진짜 보스
문제 요약
N개의 칸이 있고, 처음에는 모든 칸에 블록이 없다.
쿼리는 두 종류다.
1 x: x번째 칸에 블록을 하나 놓는다. 그 결과 모든 칸에 블록이 1개 이상 있으면, 모든 칸에서 블록을 1개씩 제거한다.2 y: 블록이 y개 이상 있는 칸의 개수를 출력한다.
처음에는 단순해 보였는데, 직접 생각해보니 꽤 까다로웠다.
처음 접근
처음에는 각 칸의 블록 개수를 배열로 관리하고,
전체에서 몇 번 1개씩 제거했는지를 minusidx 같은 변수로 관리하면 되겠다고 생각했다.
즉 실제 블록 수를 전부 직접 빼지 않고,
“전체 감소 횟수”만 따로 들고 가려는 방향이었다.
이 생각 자체는 맞는 쪽이었다.
하지만 문제는 2 y 쿼리였다.
블록이 y개 이상 있는 칸의 개수를 빠르게 구해야 하는데,
매번 모든 칸을 돌면 안 된다.
여기서 꽤 오래 고민했다.
핵심 관찰
결국 중요한 건
“현재 블록 수”를 직접 세는 게 아니라,
각 칸이 어떤 높이를 달성했는지를 세는 것이었다.
예를 들어 어떤 칸에 블록을 놓아서 누적 높이가 5가 되었다면,
그 칸은 “높이 5를 달성한 칸”이 된다.
그래서 cntarr[h]를
누적 높이 h를 달성한 칸의 개수
처럼 관리하면 된다.
그리고 전체에서 1개씩 제거된 횟수를 minusidx라고 하면,
현재 블록이 y개 이상인 칸은
누적 기준으로 y + minusidx를 달성한 칸이다.
이 관찰을 잡고 나서야 문제가 풀리기 시작했다.
처음 코드가 틀린 이유
처음에는 boolean 배열과 flag를 이용해서
“이번 기준에서 방문했는가”를 관리하려고 했다.
하지만 이 방식은 틀렸다.
왜냐하면 이 문제는 단순히
“이번 라운드에 방문했는가”를 보는 문제가 아니기 때문이다.
예를 들어 상태가
3 0 3이고, 가운데에 하나를 놓으면
3 1 3이 되어 전체 제거가 일어나고,
2 0 2가 된다.
여기서 다시 가운데에 하나를 놓으면
2 1 2가 되고 또 전체 제거가 가능해진다.
즉 같은 칸이 여러 기준에서 다시 “1 이상인 칸”이 될 수 있다.
단순 방문 체크로는 이걸 제대로 관리할 수 없었다.
수정한 핵심 코드
그래서 결국 다음처럼 바꿨다.
arr[b]++;
cntarr[arr[b]]++;
if (arr[b] == minusidx + 1) {
cnt++;
}
if (cnt == n) {
minusidx++;
cnt = cntarr[minusidx + 1];
}이 코드의 의미는 다음과 같다.
arr[b]는 b번째 칸에 지금까지 실제로 놓은 총 횟수minusidx는 전체에서 1개씩 제거한 횟수- 어떤 칸의
arr[b]가minusidx + 1이 되면, 현재 기준에서 그 칸은 블록이 1개 이상 있는 칸이 된다. - 모든 칸이 현재 기준을 달성하면
minusidx를 1 올린다. - 다음 기준에서 이미 달성한 칸 수는
cntarr[minusidx + 1]로 바로 알 수 있다.
이걸 보고 나서야 문제가 정리됐다.
느낀 점
C는 정말 고생했다.
처음에는 방문 체크 문제처럼 봤는데,
실제로는 “기준 높이 달성 여부”를 관리하는 문제였다.
내가 이걸 “달성 카운트”라고 생각했는데,
그 표현이 딱 맞는 것 같다.
이번 C에서 얻은 교훈은 이거다.
전체 감소가 있는 문제에서는 실제 값을 계속 바꾸려 하지 말고,
기준값을 따로 두고 각 원소가 그 기준을 달성했는지로 보는 방법을 생각해보자.
5. 이번 대회에서 좋았던 점
1) D를 빠르게 해결했다
C에서 오래 막히기 전에 D를 먼저 풀었고,
재배열 문제를 남은 개수가 가장 많은 문자부터 고르는 방식으로 잘 해결했다.
2) C를 끝까지 포기하지 않았다
C에서 5번 틀렸고, 시간도 90분 넘게 걸렸다.
그래도 결국 관점을 바꿔서 AC까지 갔다.
이건 꽤 의미가 있다.
오늘 C는 그냥 구현 실수 하나 고친 문제가 아니라,
문제를 보는 관점을 바꿔서 해결한 문제였기 때문이다.
3) 취업한 날에도 루틴을 지켰다
어제는 취업한 날이었다.
기분도 붕 뜰 수 있었고,
그냥 쉬어도 이상하지 않은 날이었다.
그래도 평소처럼 앳코더를 했고,
결국 1000점까지 가져왔다.
이건 꽤 기억에 남을 것 같다.
6. 아쉬웠던 점
1) B에서 전환이 조금 늦었다
작은 경우의 수는 빠르게 직접 처리하는 판단도 필요하다.
처음에 너무 일반화하려고 하면서 시간이 조금 더 걸렸다.
2) C에서 방문 체크 관점에 오래 머물렀다
처음 boolean 방문 체크로 생각한 게 오래 발목을 잡았다.
이 문제는 방문 여부가 아니라, 현재 기준 높이 달성 여부를 봐야 했다.
3) C에 시간이 너무 많이 들었다
결과적으로 맞췄지만, C 하나에 90분 넘게 쓴 건 꽤 컸다.
조금 더 빨리 minusidx와 cntarr의 의미를 정리했으면 좋았을 것 같다.
7. 다음 목표
- 전체 감소가 있는 문제에서는 기준값을 따로 두는 관점을 떠올리기
- 방문 체크와 달성 여부를 구분하기
- 작은 경우의 수 문제에서는 하드코딩도 선택지로 두기
- C에서 오래 맞아도 멘탈을 놓지 않는 건 유지하기
- 복잡한 관리 문제에서는 변수의 의미를 먼저 문장으로 정리하고 구현하기
한 줄 정리
ABC 459는 취업한 날에도 앳코더 루틴을 지켰고,
D는 빠르게 해결했지만, C에서 “방문 체크”가 아니라 “기준 높이 달성 카운트”가 필요하다는 걸 깨닫기까지 오래 걸린 대회였다.