앳코더 ABC 441 후기

카테고리 없음

앳코더 ABC 441 후기

tkd0711 2026. 1. 18. 21:33

1. 전체 총평

https://atcoder.jp/contests/abc441
이번 주 전반적인 느낌을 한 줄로 요약하면:

“A에서 off-by-one, C에서 최악 케이스 해석, D에서 변수 실수,
E에서 prefix + 세그트리/BIT 패턴을 처음 제대로 마주한 대회”

A: 1번 오답. 경계(+99 vs +100) 처리 실수.
B: 큰 문제 없이 통과.
C: “최악의 경우”를 살짝 잘못 이해해서 두 번 틀림.
이후 로직 정리하면서 적이 사케를 어떻게 배치할 수 있는지를 제대로 이해.
D: 알고리즘 자체는 맞았는데, cnt == 3처럼 상수 박아 둔 부분에서 단순 실수.
E: 완전탐(이중 루프)은 보였지만,
최적화 방향(누적합 + 세그트리/BIT)까지는 컨테스트 중에 완성 못 함.
대신 prefix → (i, j) 쌍 카운팅 → 세그/펜윅 패턴을 처음 체감.

레이팅/퍼포먼스는 아쉬울 수 있지만,
내용적으로는 “다음 단계로 가기 전에 꼭 한번 거쳐야 하는 실수들”을 한꺼번에 밟은 느낌.

2. A – 100×100 블록, off-by-one 실수

문제 요약

이론상 10^100 × 10^100 크기의 격자가 있고,
왼쪽 위가 (P, Q)인 100×100 정사각형 영역만 검은색.
나머지는 모두 흰색.
어떤 셀 (X, Y)가 검은색인지 판별하는 문제.

내가 쓴 코드 (오답)

if (p + 100 >= x && q + 100 >= y && p <= x && q <= y)
    System.out.println("Yes");
else
    System.out.println("No");

실수 포인트:

(P, Q)에서 시작해서 100개 셀을 포함하면,
- 행 인덱스: P, P+1, ..., P+99
- 열 인덱스: Q, Q+1, ..., Q+99
따라서 오른쪽/아래 경계는 P+99, Q+99가 되어야 함.

정답 조건

if (p + 99 >= x && q + 99 >= y && p <= x && q <= y)
    System.out.println("Yes");
else
    System.out.println("No");

배운 점

“개수 100개”와 “끝 인덱스”를 헷갈리면 바로 +1 실수로 이어진다.
앞으로는 이런 식으로 생각하기:
- P에서 시작해서 len개를 포함 → 끝 인덱스는 P + len - 1.

3. B – 큰 문제 없이 통과

B는 특별히 꼬이는 부분 없이,
지금까지 하던 구현/시뮬레이션 감각으로 무난하게 해결.

입력 파싱
조건에 맞는 연산/검사
1트 AC

이 문제 자체보다는,
“A, B는 안정적으로 가져가는 페이스”가 유지된다는 점을 체크하는 정도였다.

4. C – 사케/물 컵, 최악 케이스 해석 실수

문제 요약

N개의 컵, i번째 컵에 A[i] ml 액체.
정확히 K개의 컵에 사케, 나머지는 물.
어떤 컵이 사케인지 모름.
몇 개의 컵을 골라서 전부 마실 수 있다.
어떤 사케 배치에서도 최소 X ml 이상의 사케를 마시도록 하기 위해
마셔야 하는 컵의 최소 개수를 구하기.
불가능하면 -1.

내가 처음 생각한 방식 (오답)

정렬 후, 나는 이렇게 생각했음:

“작은 컵들 몇 개가 사케일 때가 최악이니까,
작은 것부터 K개를 사케로 보고,
그 중 최소 몇 개를 합쳐야 X가 되는지를 보자.”

그래서 썼던 코드:

Arrays.sort(arr);

long sum = 0;
for (int i = 0; i < m; i++) {
    sum += arr[i];
    if (sum >= x) {
        int good = i + 1;         // 사케 컵 개수
        System.out.println(good + n - m); // 물 컵 + 사케 컵
        return;
    }
}
System.out.println(-1);

하지만 이건 “사케 배치가 이미 arr[0..K-1]에 고정된 경우”에 대한 이야기라,
문제가 요구하는 “모든 배치에 대해”와는 미묘하게 다르다.

진짜 최악 케이스 해석

문제의 핵심은:

내가 어떤 규칙으로 컵을 골라 마셔도,
그걸 본 ‘적’이 사케를 가장 불리하게 배치할 수 있다.

적은 이렇게 행동할 수 있다:

내가 고른 컵들 중에서는 가능한 한 작은 용량들만 사케로,
내가 고르지 않은 컵들 중에서는 가능한 한 큰 용량들을 사케로.

즉, 진짜 최악 배치는:

전체에서 가장 작은 K개에 사케가 몰려 있는 경우.
내가 어떤 컵을 고르든,
“내가 마신 컵들 중에서 작은 애들만 사케”가 될 수 있다는 뜻.

그래서:

전체 배열을 정렬.
가장 작은 K개: arr[0..K-1]이 전부 사케라고 가정해도 손해 보지 않는다.
그 안에서 “얼마나 마셔야 X 이상이 되는지”를 계산해야 한다.

정답 방향

Arrays.sort(arr);

int[] sake = new int[m]; // m = K
for (int i = 0; i < m; i++) sake[i] = arr[i]; // 작은 K개

long sum = 0;
int cnt = 1;
for (int i = m - 1; i >= 0; i--) {  // 작은 K개 중 '큰 것부터'
    sum += sake[i];
    if (sum >= x) {
        System.out.println(cnt + (n - m));
        return;
    }
    cnt++;
}
System.out.println(-1);

의미:

“사케가 가장 불리하게 작은 곳에 몰려 있다”고 보고,
그 작은 K개 중에서 큰 것부터 cnt개를 마셨을 때 X 이상이 되는 최소 cnt를 찾는다.
실제로는 물 컵도 함께 마셔야 할 수 있으므로,
- 사케 컵 cnt개 + 물 컵 (N - K)개 모두 마셔야 하는 최악까지 감안해
  답은 cnt + (N - K)가 된다.

C에서 배운 것

“최악의 경우”를 생각할 때,
- “배치까지 적이 정할 수 있다”는 상황이면,
  내 직관보다 한 단계 더 빡센 조건을 가정해야 한다.
특히 “K개만 특별한 속성이 있고, 어떤 K개인지는 모른다” 타입 문제에서는:
- 전체를 정렬한 뒤,
- “가장 불리한 K개”에 특성이 몰려 있다고 보고 생각하는 패턴이 자주 쓰인다.

5. D – 로직은 맞았는데, 변수 대신 상수를 박은 실수

문제 요약

유향 그래프 (정점 N, 간선 M, out-degree ≤ 4).
간선 i는 U[i] → V[i], 비용은 C[i].
정점 1에서 시작해서 정점 v까지 가는 경로 중에서,
- 정확히 L개의 간선을 지나고,
- 비용 합이 S 이상 T 이하인 경로가 존재하는 모든 v를 찾는 문제.

실수한 부분

로직을 짜면서,
“간선을 몇 개 지나왔는지”를 cnt 같은 변수로 들고 있었는데,
종료 조건을 이렇게 썼다고 했다:

if (cnt == 3) {
    if (s <= pri && pri <= t) {
        set.add(go);
    }
    continue;
}

여기서 3은 그냥 디버깅/test용으로 임시 박았던 수 같은데,
최종 코드에서 L을 사용해야 할 자리에 그대로 남아버린 것.

정답은 당연히:

if (cnt == l) {
    if (s <= pri && pri <= t) {
        set.add(go);
    }
    continue;
}

D에서 배운 것

알고리즘/아이디어는 맞았는데,
상수 3을 박아 둔 상태로 변수 L로 바꾸지 않은 단순 실수.
앞으로는:
- 문제에서 준 기호(L, K, N 등)를
  코드 변수 이름으로 그대로 사용하는 습관을 더 강화하는 게 좋을 듯.
- 코드 안에 “마법의 숫자(3, 100 같은 하드코딩 숫자)”가 보이면
  한 번 더 의심해보기.

6. E – A가 B보다 많은 부분 문자열 개수 + 자료구조 맛보기

문제 요약

문자열 S (길이 N), 문자 종류는 A, B, C.
모든 부분 문자열 중에서
“A의 개수가 B의 개수보다 많은” 부분 문자열 개수를 구하는 문제.
부분 문자열의 시작/끝 위치가 다르면, 내용이 같아도 다른 하나로 센다.

대회 중 생각 흐름

가장 먼저 떠오른 건 이중 for 완전탐:
- O(N^2)로 모든 (l, r)을 돌면서 #A > #B 여부 체크 → N 크기 때문에 불가능.
누적합, 투 포인터, 세트/트리셋 활용 등의 방법을 떠올렸지만,
- “C가 0처럼 행동하는데 이게 깔끔하게 정리될까?”
- “이중포문을 어떻게 줄일 수 있지?”에서 막혔음.

정리된 아이디어 (prefix + 세그트리/BIT)

핵심 트릭:

문자를 숫자로 변환:
- A → +1, B → -1, C → 0
누적합 pref[i] 정의:
- pref[0] = 0
- pref[i] = val[1] + ... + val[i]
그러면 부분 문자열 S[l..r]에 대해:
- sum(l..r) = pref[r] - pref[l-1]
- 이 값이 #A - #B가 된다.
조건 #A > #B는:
- pref[r] - pref[l-1] > 0
- ⇔ pref[l-1] < pref[r]
즉, 정답은:

인덱스 0 ≤ i < j ≤ N 에 대해
pref[i] < pref[j]인 (i, j) 쌍들의 개수

이제 해야 할 일은:

prefix 배열 pref[0..N]이 있을 때,
“i < j이며, pref[i] < pref[j]”인 쌍 개수를 O(N log N)에 세기

이건 전형적인 BIT/세그트리 카운팅 패턴:

pref 값들을 좌표압축.
왼쪽에서 오른쪽으로 j를 하나씩 보고,
- “지금까지 나온 pref[i]들 중,
  pref[i] < pref[j]인 개수”를 세그/펜윅으로 구해서 정답에 더함.
- 그리고 현재 pref[j]를 트리에 +1.

이 패턴은 inversion count(역순 쌍 세기)와 거의 동일한 구조라서,
세그트리/BIT를 본격적으로 쓰는 첫 단계로 딱 좋은 문제.

E에서 배운 것

“부분 문자열” + “A, B 개수 비교” 타입 문제는,
누적합 + 부등식(prefix 차이) 로 바꿔서 푸는 경우가 많다.
이중 루프 완전탐의 구조가:
- (l, r) → (i, j) 쌍
- 조건식 → prefix 부등식
- → 세그트리/BIT를 사용한 카운팅 문제로 변형되는 패턴을 처음 제대로 체감.

7. 관련 백준 연습 문제 정리

E 타입 (누적합 + 세그/BIT)

E에서의 prefix+자료구조 감각을 같이 키울 수 있는 문제들:

E(세그/BIT 느낌):
10986 (나머지 합) – Gold 3
2015 (수들의 합 4) – Gold 4
2042 (구간 합 구하기) – Gold 1
1517 (버블 소트) – Platinum 5
3653 (영화 수집) – Platinum 4

10986, 2015로 “누적합 + 카운팅” 감각을 잡고,
2042로 세그트리 기본기,
그 다음 1517, 3653으로 (i, j) 쌍 카운팅/응용 패턴까지 가면
이번 E에서 느꼈던 “세그트리/펜윅이 여기서 이렇게 쓰이는구나”가 훨씬 자연스러워질 것 같다.

8. 다음 주를 위한 작은 목표

A/B:
- off-by-one, 하드코딩 상수 실수 조금만 줄이기.
- “끝 인덱스 = 시작 + 길이 - 1” 한 번만 더 의식하기.
C/D:
- “최악 배치/조건”을 명확하게 글로 써 보고 정리하는 습관 들이기.
- 이분 탐색/그리디 문제에서는 특히 중요.
E:
- 이번에 본 prefix + 세그/BIT 패턴을
  BOJ 몇 문제로 연습해 보고,
  다음에 비슷한 냄새가 날 때 바로 떠올릴 수 있도록 만들기.

이번 주는 실수도 있었지만,
그만큼 “아 이런 생각을 앞으로는 먼저 해야겠구나”를 많이 남긴 주간이라
길게 보면 꽤 값진 회고가 된 것 같다.

현재글앳코더 ABC 441 후기

tkd0711 님의 블로그

tkd0711 님의 블로그 입니다.

앳코더, AtCoder,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

tkd0711 님의 블로그