`위 문제 유형은 Dynamic Programming이다.
규칙을 찾아서 적용하면 되겠다.
과정
-
선언
- 2*n 의 최대값이 246912이므로 246913의 소수 여부 배열(boolean)
- 위와 같은 크기의 int배열 선언하여 1부터 소수가 몇 개 있는지 저장
-
값 할당
- 에라토스테네스 체 원리 이용하여 소수 여부를 true로 바꿈
- 2부터 반복문을 이용해 false가 나올 때마다 count를 올려주는 식으로 코드를 구성
-
최종 풀이
- 수를 입력받아 2*n까지의 소수 개수에서 n개까지 소수 개수를 빼고 정답 출력
이 문제는 python으로 풀었음.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import sys
input = sys.stdin.readline
N = int(input())
dp = [0 for _ in range(N+3)]
arr = [0 for _ in range(N+3)]
for k in range(1,N+1):
arr[k] = int(input())
dp [1] = arr[1]
dp [2] = arr[1] + arr[2]
dp [3] = max(arr[1] + arr[3] ,arr[2] + arr[3])
for i in range(4, N+1):
dp[i] = max( dp[i-3] + arr[i-1] + arr[i] , dp[i-2] + arr[i] )
print(dp[N])
|