AtCoder Beginner Contest 439 회고 (tkd0711)
https://atcoder.jp/contests/abc439
- 날짜: 2026-01-03 (Sat)
- 결과: A ~ C 1트 AC, D는 런타임/메모리 이슈 포함 5번 틀린 후 AC, E는 아이디어까지만
- 최종 스코어: 1025 pts
1. 전체 총평
이번 ABC 439 전반적인 느낌:
- A: 워밍업 문제, 1:19 컷.
- B: 해피 넘버(happy number) 스타일 구현 문제.
- C:
x^2 + y^2 = k꼴 good integer 카운트, 브루트포스 + 범위 줄이기. - D:
- 조건이
Ai : Aj : Ak = 7 : 5 : 3+ 인덱스 조건(min/max가 j) + 값 범위10^9. - 처음에 값 범위를 잘못 보고 배열로 갔다가 런타임/메모리 관련해서 5번 틀림.
- 이후 HashMap + prefix/suffix 카운팅으로 정리해서 AC.
- 조건이
- E:
- 선분 교차를 피하면서 최대한 많이 고르는 문제.
Ai기준 정렬 후Bi에 대해 LIS를 구하는 전형적인O(N log N)문제라는 것까지는 파악.- 다만 이걸 정리해서 코드로 옮기기 전에 시간이 끝나서 미제출.
ABC는 비교적 깔끔하게 풀었고,
D에서 많이 틀리긴 했지만 끝까지 붙잡고 맞춘 점,
E에서 LIS 아이디어까지는 도달했다는 점이 이번 컨테스트의 포인트였다.
2. A – 2^n - 2n (1:19 컷)
https://atcoder.jp/contests/abc439/tasks/abc439_a
아이디어
- 입력:
n - 출력:
2^n - 2n. a = 2에서 시작해서n-1번 2를 곱해2^n을 만든 뒤, 마지막에a - 2*n출력.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int a = 2;
for(int i = 1; i < n; i++){
a = a * 2;
}
System.out.println(a - (2*n));
}
}
느낌
1:19에 1트 AC.
딱 워밍업용 문제였고, 특별히 할 말은 없는 수준.
3. B – Happy Number 스타일, 사이클 체크
https://atcoder.jp/contests/abc439/tasks/abc439_b
문제 요약
문자열로 양의 정수
s가 주어진다.각 자릿수의 제곱을 모두 더해서 새로운 수를 만들고, 이 과정을 반복.
최종적으로 1이 되면
"Yes",중간에 이미 나왔던 수가 다시 나오면 사이클이므로
"No".
아이디어
현재 값을 문자열로 두고:
각 자릿수를 하나씩 꺼내서 제곱 후 더해
temp를 만든다.sum = temp,str = temp + ""로 갱신.
HashSet으로 지금까지 나온 값들을 관리:
sum == 1이면"Yes".sum이 이미 Set에 있으면 사이클이므로"No".
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String str = st.nextToken();
int sum = 0;
HashSet<Integer> set = new HashSet<>();
while(sum != 1){
int temp = 0;
for(int i = 0; i < str.length(); i++){
int a = str.charAt(i) - '0';
temp += a * a;
}
sum = temp;
str = temp + "";
if(set.contains(sum)){
System.out.println("No");
return;
}
set.add(temp);
}
System.out.println("Yes");
}
}
타임라인 & 느낌
1:19 → 8:39 사이에 해결 (약 7분).
구현 난이도는 높지 않았고,
char → int캐스팅만 조심하면 되는 문제.전형적인 happy number 스타일 문제라 부담 없이 넘어감.
4. C – x^2 + y^2 = k 꼴 good integer 카운트
https://atcoder.jp/contests/abc439/tasks/abc439_c
문제 요약
정수
N이 주어질 때,양의 정수
x, y가 존재해서x < y이고x^2 + y^2 = k를 만족하는k를 good integer라고 한다.1 ≤ k ≤ N인 good integer를 모두 나열하고, 개수도 출력.
아이디어
조건:
x < y,x^2 + y^2 ≤ N.단순 브루트포스지만, 범위를 줄여서 돌리면 충분히 가능.
루프 설계:
i를 1부터 올리면서(i * i) * 2 <= N인 범위까지만 (최소값이i^2 + (i+1)^2인 점 이용).j는i+1부터 시작해서i*i + j*j <= N인 동안만 증가.
sum = i*i + j*j에 대해arr[sum]++.마지막에
arr[k] == 1인 k만 good integer로 보고 출력.
(이번 구현에서는 “딱 한 쌍으로만 표현되는 k”만 good으로 취급.)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int num = 10000000;
int[] arr = new int[num + 20];
for(int i = 1; (i * i) * 2 <= n; i++){
for(int j = i + 1; i * i + j * j <= n; j++){
int a = i * i;
int b = j * j;
arr[a + b]++;
}
}
ArrayList<Integer> list = new ArrayList<>();
for(int i = 1; i <= n; i++){
if(arr[i] == 1){
list.add(i);
}
}
System.out.println(list.size());
for(int i = 0; i < list.size(); i++){
sb.append(list.get(i)).append(" ");
}
System.out.println(sb);
}
}
타임라인 & 느낌
8:39 → 21:13 사이에 해결 (대략 12~13분).
핵심은 범위를 줄여서 브루트포스하는 것:
(i*i)*2 <= n조건으로 i 상한 설정.i*i + j*j <= n인 j만 돌도록.
int[1e7]배열 하나 정도는 자바에서도 여유 있음.아이디어도 직관적이고, 구현도 크게 꼬이지 않았다.
5. D – Kadomatsu Subsequence: 5번 틀리고 맞춘 문제
https://atcoder.jp/contests/abc439/tasks/abc439_d
문제 요약
길이
N의 수열A = (A1, ..., AN)이 주어진다.다음 조건을 만족하는
(i, j, k)의 개수를 구해야 한다.
1 ≤ i, j, k ≤ NAi : Aj : Ak = 7 : 5 : 3
→ 어떤 정수 x가 있어서Ai = 7x,Aj = 5x,Ak = 3x.min(i, j, k) = j또는max(i, j, k) = j.
- 제약:
N ≤ 3 * 10^5,Ai ≤ 10^9.
관찰
Aj가 5의 배수일 때만 의미가 있다.Aj = 5x라고 놓으면:Ai = 7x,Ak = 3x형태가 되어야 한다.
인덱스 조건 두 가지:
max(i, j, k) = j→ j가 가장 뒤에 있는 경우 (i, k < j)min(i, j, k) = j→ j가 가장 앞에 있는 경우 (i, k > j)
결국, j를 기준으로:
앞에 있는
3x,7x개수뒤에 있는
3x,7x개수를 각각 세서 조합을 곱해주면 된다.
첫 시도 – 배열로 하다가 런타임/메모리 문제 (5번 틀림)
처음에는 이렇게 접근했다:
Ai = 3x→x = Ai / 3Ai = 7x→x = Ai / 7그래서
pre3[x],pre7[x]같은 배열을 만들어서 앞에서 본 횟수를 저장하고,Aj % 5 == 0일 때num = Aj / 5에 대해pre3[num] * pre7[num]을 더해주는 방식.
예시 코드 형태:
int bignum = 1000000000;
int[] pre7 = new int[bignum/7 + 2];
int[] pre3 = new int[bignum/3 + 2];
문제는 여기서 터졌다:
bignum/3 ≈ 3.3e8,bignum/7 ≈ 1.4e8수준이라이런 배열을 여러 개 잡는 순간 메모리도 크고,
실제 동작에서도 런타임/메모리 관련 에러가 계속 났다.이 방식으로 시도하다가 총 5번이나 틀림.
여기서 얻은 교훈:
값 범위가
10^9까지 나오면,
단순히 그걸 인덱스로 쓰는 배열을 만드는 선택은 거의 항상 위험하다.
먼저 “배열이 가능한지” 체크하고, 안 되면 HashMap이나 좌표압축을 떠올렸어야 한다.
수정된 접근 – HashMap + prefix/suffix 카운팅
결국, 배열 대신 HashMap을 쓰는 방향으로 수정했다.
premap: j 기준 왼쪽에서 본 값들의 개수sufmap: j 기준 오른쪽에서 본 값들의 개수
j가 가장 뒤인 경우 (max(i, j, k) = j)
앞에서부터 i = 0 → n-1로 진행:
현재 값
cur = A[i]에 대해cur % 7 == 0이면premap[cur]++cur % 3 == 0이면premap[cur]++두 조건 다 만족하는
cur % 21 == 0은 중복이므로-1로 보정
그리고
cur % 5 == 0이면:x = cur / 5c3 = premap.getOrDefault(3 * x, 0)c7 = premap.getOrDefault(7 * x, 0)cnt += c3 * c7
이렇게 하면, j가 세 인덱스 중 가장 뒤에 있을 때의 경우가 모두 포함된다.
j가 가장 앞인 경우 (min(i, j, k) = j)
뒤에서부터 i = n-1 → 0으로 진행:
sufmap에 대해 위와 같은 로직을 그대로 수행.cur % 5 == 0이면:x = cur / 5c3 = sufmap.getOrDefault(3 * x, 0)c7 = sufmap.getOrDefault(7 * x, 0)cnt += c3 * c7
최종 코드 (뼈대)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
long cnt = 0L;
// j가 최대인 경우
HashMap<Integer,Integer> premap = new HashMap<>();
for(int i = 0; i < n; i++){
int cur = arr[i];
if(cur % 7 == 0){
premap.put(cur, premap.getOrDefault(cur, 0) + 1);
}
if(cur % 3 == 0){
premap.put(cur, premap.getOrDefault(cur, 0) + 1);
}
if(cur % 21 == 0){
premap.put(cur, premap.getOrDefault(cur, 0) - 1);
}
if(cur % 5 == 0){
int x = cur / 5;
long c3 = premap.getOrDefault(3 * x, 0);
long c7 = premap.getOrDefault(7 * x, 0);
cnt += c3 * c7;
}
}
// j가 최소인 경우
HashMap<Integer,Integer> sufmap = new HashMap<>();
for(int i = n - 1; i >= 0; i--){
int cur = arr[i];
if(cur % 7 == 0){
sufmap.put(cur, sufmap.getOrDefault(cur, 0) + 1);
}
if(cur % 3 == 0){
sufmap.put(cur, sufmap.getOrDefault(cur, 0) + 1);
}
if(cur % 21 == 0){
sufmap.put(cur, sufmap.getOrDefault(cur, 0) - 1);
}
if(cur % 5 == 0){
int x = cur / 5;
long c3 = sufmap.getOrDefault(3 * x, 0);
long c7 = sufmap.getOrDefault(7 * x, 0);
cnt += c3 * c7;
}
}
System.out.println(cnt);
}
}
D에서 얻은 교훈
값 범위가
10^9같은 식으로 크면:“배열 인덱스로 그대로 쓸 수 있나?”를 먼저 생각해야 한다.
안 되면 바로 HashMap, TreeMap, 좌표압축 등을 고려하는 습관이 필요.
“기준 인덱스 하나(j)를 잡고, 앞/뒤에서 카운트해서 조합을 곱하는 패턴”이 자주 나오는 테크닉이라는 걸 다시 느꼈다.
5번이나 틀리긴 했지만, 그만큼 강하게 기억에 남는 실수라
비슷한 패턴의 문제에서 같은 실수를 반복할 가능성은 많이 줄어들 것 같다.
6. E – Kite: 교차하지 않는 선분 최대 개수 (아이디어까지만)
https://atcoder.jp/contests/abc439/tasks/abc439_e
문제 요약 (간단 정리)
사람 i는
(Ai, 0)에 서 있고, 연은(Bi, 1)에 있다.사람 i는 이 두 점을 잇는 선분을 만든다.
두 사람 i, j에 대해:
- 선분
(Ai, 0)-(Bi, 1)과(Aj, 0)-(Bj, 1)이 교차하거나 끝점이 닿으면 동시에 연을 날릴 수 없다.
- 선분
이 제약을 지키면서, 동시에 연을 날릴 수 있는 사람 수의 최댓값을 구하는 문제.
관찰 & 아이디어
선분 교차 조건을 생각해 보면:
x축(y=0)에서의 순서와 y=1에서의 순서가 “엇갈리면” 교차하게 된다.
예를 들어
Ai < Aj인데Bi > Bj이면 두 선분이 교차.
따라서:
사람들을
Ai기준으로 오름차순 정렬한다.이 정렬 순서대로
Bi만 뽑아서 수열을 만든다.이
Bi수열에서 증가 부분 수열(LIS)의 최대 길이를 구하면 된다.
N ≤ 2 * 10^5 이므로,
LIS를O(N log N)에 구하는 전형적인 lower_bound/배열 방식으로 충분히 가능.
이번 컨테스트에서의 진행 상황
문제를 읽고,
“선분 교차 여부 → 순서가 뒤집힘 → 정렬 + LIS”라는 구조라는 것까지는 파악했다.결론:
Ai로 정렬그 순서대로
Bi를 나열한 뒤, LIS 길이 = 정답
라는 틀까지는 도달.
하지만,
같은
Ai또는 같은Bi가 있을 때 정렬/비교를 어떻게 둘지,교차 조건에 “끝점이 닿는 경우”까지 포함된다고 했으니,
LIS에서strict/non-strict를 어떻게 둘지 등디테일을 마저 정리하고 코드로 옮기기 전에 시간이 끝났다.
정리하면:
E는 “N log N LIS 문제”라는 것까지는 알았고,
거의 다 왔는데, 구현/디버깅까지는 못 가서 제출을 못 했다.
다음에 비슷한 유형 나오면 바로 LIS 코드까지 찍어낼 수 있도록 연습할 필요가 있음.
7. 이번 대회 전체에서 느낀 점
A, B, C는 이제 꽤 안정적으로 1트 AC를 노릴 수 있는 구간에 들어온 것 같다.
D에서는:
인덱스 조건(min/max = j)을 앞/뒤 카운트로 분리해서 세는 방식,
값 범위에 따라 배열을 쓸지, HashMap/좌표압축을 쓸지 판단하는 부분
두 가지를 다시 생각하게 됐다.
E에서는:
“선분 교차 → 정렬 + LIS”라는 전형적인 패턴을 실제 컨테스트에서 직접 캐치했다는 점이 의미 있었다.
아이디어까지는 갔는데 구현을 못 해서 아쉬움이 남는다.
WA/RE를 여러 번 맞더라도,
왜 이런 선택을 했고,
무엇이 잘못됐는지를 정리해두면
확실히 다음에 도움이 된다는 걸 다시 느꼈다.
8. 앞으로의 계획
단기 목표:
이번 D처럼 “비율/배수 + 카운팅 + 인덱스 조건”이 섞인 문제들을 몇 개 더 풀어보기.
이번 E처럼 “정렬 + LIS”로 귀결되는 문제들을 따로 모아서 연습하기.
- 특히, 값이 크거나 좌표가 섞여 있을 때
“무엇을 기준으로 정렬하고, 무엇에 대해 LIS를 취할지”를 빨리 잡는 연습.
- 특히, 값이 크거나 좌표가 섞여 있을 때
값 범위가 큰 문제를 보면,
배열 대신 HashMap/좌표압축을 떠올리는 습관 들이기.
컨테스트 운영:
A~C는 최대한 빠르게 안정적으로 가져가고,
남는 시간과 멘탈을 D 이후 문제에 집중할 수 있도록 시간 분배 연습.
전체적으로는,
ABC는 잘 풀었고, D에서 많이 맞으면서도 끝까지 잡고 있었고,
E에서 “아 이거 LIS였는데…” 하는 아쉬움까지 포함해서
다음 단계를 위한 연습이 된 컨테스트였다.