1885번 - 비부분수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 219 | 91 | 76 | 45.783% |
문제
수열에서 몇 개의 수를 순서대로 골라 만들 수 있는 수열을 부분수열이라고 한다. 예를 들어 수열 S = [1, 5, 3, 2, 5, 1, 3, 4, 4, 2, 5, 1, 2, 3]에서 첫 번째, 다섯 번째, 일곱 번째, 열 번째 수를 고르면 부분수열 p = [1, 5, 3, 2]을 만들 수 있다.
수열 S와 임의의 부분수열 p가 주어졌을 때, 모두 몇 가지 방법으로 S에서 고른 수로 p를 구성할 수 있는지에 관한 문제는 많이 다루어진 문제이므로, 이번에는 반대의 경우를 생각해 보자. 수열 S가 주어지고, 이 수열에서 만들 수 없는 부분수열에 관해 생각해 보는 것이다.
부분수열이 충분히 길면 물론 만들어 낼 수 없을 것이다. 그럼 만들어 낼 수 없는 부분수열 중 가장 짧은 것의 길이는 얼마일까? 이를 알아내는 프로그램을 작성하라.
입력
첫 줄에 두 정수 n과 k가 주어진다. (1 ≤ n ≤ 100,000. 1 ≤ k ≤ 10,000) n은 수열 S의 길이이고, k는 수열 내에 존재하는 수들의 범위이다. 즉, S가 1이상 k이하의 정수들로만 이루어져 있음을 나타낸다. 둘째 줄부터는 S를 이루는 수들이 한 줄에 한 개씩 차례로 주어진다.
출력
첫 줄에 S에 존재하지 않는 부분수열 중 가장 짧은 것의 길이를 출력한다.
예제 입력 1
14 5 1 5 3 2 5 1 3 4 4 2 5 1 2 3
예제 출력 1
3
힌트
1이상 5이하의 정수들로 만들 수 있고 길이가 1, 2인 수열은 모두 S 내에 부분수열로서 존재한다. 길이가 3인 부분수열 중 [2, 2, 4]는 수열 내에 존재하지 않는다.
출처
Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO US Open 2004 Contest > Green 2번
- 문제를 번역한 사람: author5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호