35153번 - 시니어 개발자 동우의 직행 취업일기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 93 | 43 | 29 | 49.153% |
문제
직행은 취업 과정에서 발생하는 불필요한 복잡함을 줄이기 위해 만들어진 채용 서비스이다. 여러 채용 사이트에 흩어져 있는 채용 공고를 대규모 크롤링으로 수집하고, 자연어 처리(NLP) 기술을 활용해 플랫폼별, 직무별로 정리하여 제공하고 있다. 이를 통해 구직자는 반복적인 검색과 비교 과정 없이, 자신에게 맞는 채용 공고를 보다 빠르게 탐색할 수 있다.
이러한 방식으로 설립 1년 만에 연간 방문자 수 100만 명을 달성하며, 국내 채용 서비스 기준 상위 5위권에 진입했다. 직행은 소프트웨어와 데이터 기술을 기반으로 취업 준비 과정을 단순화하고, 궁극적으로 ‘직장인의 행복’에 기여하는 것을 목표로 한다.
시니어 개발자인 동우는 대학원에서 탈출해 직행에 취업하려고 한다. 직행의 대표인 재헌이는 동우의 실력 검증을 위해 직행 서비스에서 제공하는 회사들을 분류하라는 과제를 냈다. 구체적으로 각 회사들을 정점으로 생각해 트리에 배치하려고 한다. 이때 다음 조건을 만족해야 한다.
먼저 트리의 지름이란, 트리에서 임의의 두 회사 정점 사이의 경로 중 가장 긴 경로를 말한다. 만약 그러한 경로가 여러 개라면, 모두 트리의 지름이 된다.
트리의 지름의 개수란, 트리의 지름의 길이가 $d$일 때, 트리에서 두 회사 정점 사이의 거리가 $d$인 정점 쌍의 개수이다. 이때, 두 회사의 순서만 다른 것은 하나로 센다.
양의 정수 $N$이 하나 주어지면, 트리의 지름의 개수가 $N$개이며 모든 간선의 길이가 $1$인 트리 하나를 구성하는 프로그램을 작성하시오.
입력
첫 번째 줄에 트리의 지름의 개수 $N(1\le N\le 10^{11})$이 주어진다.
출력
첫 번째 줄에 정점의 개수 $V$를 출력한다.
두 번째 줄부터 $V-1$ 줄에 걸쳐 두 정점 $u,v(1\le u,v\le V$; $u\ne v)$를 공백으로 구분하여 출력한다.
단, 원활한 채점을 위해 $2\le V\le 10^6$을 만족해야 하며, 트리를 이루고 있어야 한다. 또한 최근 살이 찐 동우는 무거운 것을 싫어하기 때문에, 차수(직접 연결된 정점의 개수)가 $4$ 이상인 무거운 정점은 $4$개 이하여야 한다. 만약 그렇지 않은 출력을 한 경우 틀렸습니다가 반환된다.
조건을 만족하는 답이 여러 개 있다면 그중 아무거나 하나 출력한다.
예제 입력 1
1
예제 출력 1
2 1 2
트리의 지름의 길이는 $1$이며, 트리의 지름은 $\left\{ 1,2 \right\}$으로 $1$개다.
예제 입력 2
1
예제 출력 2
3 1 2 2 3
트리의 지름의 길이는 $2$이며, 트리의 지름은 $\left\{ 1,3 \right\}$으로 $1$개다. 예제 1과 같은 입력이지만, 여러 정답이 있을 수 있다.
예제 입력 3
6
예제 출력 3
5 1 2 1 3 1 4 1 5
트리의 지름의 길이는 $2$이며, 트리의 지름은 $\left\{ 2,3 \right\}$, $\left\{ 2,4 \right\}$, $\left\{ 2,5 \right\}$, $\left\{ 3,4 \right\}$, $\left\{ 3,5 \right\}$, $\left\{ 4,5 \right\}$로 $6$개다.
예제 입력 4
15
예제 출력 4
7 1 7 2 7 3 7 4 7 5 7 7 6
예제 입력 5
16
예제 출력 5
15 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
예제 입력 6
18
예제 출력 6
18 13 14 4 15 18 5 12 2 5 16 7 6 3 13 9 18 17 11 7 1 4 18 2 5 18 7 8 11 10 7 13 18 5 11
출처
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 B번
- 문제를 만든 사람: kidw0124
- 문제를 번역한 사람: foxpython
- 문제를 검수한 사람: cywohoy, ezh8n, foxpython, mathjuny, sshs29hanul, tlsdydaud1, utilforever, yijw0930
채점 및 기타 정보
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호