34805번 - 코드 복원하기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 64 | 25 | 23 | 53.488% |
문제
달구의 프로그램은 $0$에서 $9$까지의 숫자로만 이루어진 코드를 비밀번호로 이용한다. 사용자의 보안을 위해, 달구의 프로그램은 길이 $N$의 비밀번호 $s$에 대해 $a_i = h(s_is_{i+1}\cdots s_{i+L-1})$로 해싱하여 만든 수열 $a_1$, $a_2$, $\cdots$, $a_{N-L+1}$을 파일에 저장한다.
이때, $s_is_{i+1}\cdots s_{i+L-1}$은 $s$의 $i$ 번째 숫자 부터 $i+L-1$ 번째 숫자까지를 이어 붙인 문자열이며, 어떤 숫자로만 이루어진 문자열 $t$에 대한 해시 함수 $h(t)$는 다음과 같다.
$$h(t) = \sum_{i=1}^{|t|}{t[i] \times 17^{(|t|-i)}} \pmod{10^9+7}$$
$t[i]$는 $t$의 $i$번째 문자이다. 문자 0, 1, 2, $\cdots$, 9는 각각 정수 $0$, $1$, $2$, $\cdots$, $9$ 로 대응된다.
모든 수열과 문자열의 인덱스는 $1$부터 시작한다.
이 방식이 안전하다고 생각하는 달구를 위해 코드를 복원해보자.
입력
첫째 줄에 정수 $N$과 $L$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$; $1 \le L \le \lfloor \displaystyle\frac{N}{2}\rfloor$)
둘째 줄에 수열 $a_1$, $a_2$, $\cdots$, $a_{N-L+1}$이 공백으로 구분되어 주어진다. ($0 \le a_i \lt 10^9+7$)
비밀번호를 복원할 수 있는 수열만 입력으로 주어진다.
출력
첫째 줄에 복원한 달구의 비밀번호를 출력한다.
복원 가능한 비밀번호가 여러 개 존재할 경우 사전순으로 가장 앞서는 비밀번호를 출력한다.
예제 입력 1
12 2 23 104 42 139 59 137 18 26 154 23 102
예제 출력 1
162838119160
예제 입력 2
4 2 37 58 123
예제 출력 2
2374
$s$=2374 인 경우, $a_1 = 17 \times 2 + 3 = 37$, $a_2=17 \times 3 + 7= 58$, $a_3=17\times 7 +4=123$ 으로, 입력에서 주어진 값과 같다. 또한 이는 사전순으로 가장 앞선 문자열이다.
출처
University > DGIST > 2025 DGIST 알고리즘 경진대회 D번
- 문제를 만든 사람: haruki291sa
- 문제를 검수한 사람: ksoosung77, leo020630, tlsdydaud1, tony9402
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호