출처 : https://www.acmicpc.net/problem/15966
군계일학 성공서브태스크
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (언어별 추가 시간 없음) | 256 MB | 1497 | 266 | 213 | 63.582% |
문제
효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.
수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야한다.
길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라.
입력
첫 째줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에, ai (1 ≤ i ≤ N, 1 ≤ ai ≤ 1,000,000)이 주어진다.
출력
수열에서 뽑아낼 수 있는 가장 긴 군계일학 수열의 길이를 출력한다.
서브태스크 1 (20점)
- N ≤ 10
서브태스크 2 (15점)
- N ≤ 1,000
서브태스크 3 (65점)
- 문제에서 주어진 제약 조건 외 조건 없음
예제 입력 1
6 1 2 3 4 5 6
예제 출력 1
6
예제 입력 2
3 1 5 2
예제 출력 2
2
출처
High School > 부산일과학고 > BSIS배 Code Festival E번
- 문제의 오타를 찾은 사람: jh05013
채점
- 예제는 채점하지 않는다.
풀이
https://github.com/Zeta611/Baekjoon/blob/master/15966%20%EA%B5%B0%EA%B3%84%EC%9D%BC%ED%95%99.py
를 참조했습니다. map 과 배열을 적절히 섞어야 하는 문제입니다. 자세한 내용은 소스코드를 참조해주세요!!
소스코드
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 | #-*- coding: utf-8 -*- n = input() num_arr = map(int, raw_input().split()) # 최대 길이를 기록하는 배열 long_arr = [1] * n # 숫자 : 숫자의 배열에 해당하는 인덱스 -> key : value 로 넣는다. num_idx_map = {num_arr[0]: 0} max_long = 1 for i in xrange(1, n): # 현재 숫자보다 1 작은 숫자가 존재하면 # 해당 숫자의 인덱스의 길이에 + 1 을 한 값을 현재 숫자의 길이로 설정 if num_arr[i] - 1 in num_idx_map: long_arr[i] = long_arr[num_idx_map[num_arr[i] - 1]] + 1 # 현재 숫자보다 1 작은 숫자가 없으면, 길이를 1로 설정 else: long_arr[i] = 1 # max 보다 현재 숫자의 길이가 크면 갱신 if long_arr[i] > max_long: max_long = long_arr[i] # map 에 현재 숫자와 인덱스를 넣어준다 num_idx_map[num_arr[i]] = i print max_long | cs |