No. 11055
1. Problem
2. My Solution
- 가장 긴 증가하는 부분 수열 원리 응용
- i 번째 수열 원소까지 존재할 때 최대값을 dp에 저장
- 첫 번째 방법
- dp 의 초기값을 0으로 초기화했을 경우 '2 1 2' 입력의 출력으로 3이 아닌 2가 출력
import sys
n = int(sys.stdin.readline().rstrip())
seqeunce = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [0] * n
dp[0] = seqeunce[0]
for i in range(1,n):
for j in range(i):
if seqeunce[i] > seqeunce[j]:
dp[i] = max(dp[i], dp[j]+seqeunce[i])
print(max(dp))- 두 번째 방법
- 자신보다 작은 원소가 존재하지 않을 때 자기 자신의 값을 최대값으로 갖도록 dp 초기값 설정
import sys
n = int(sys.stdin.readline().rstrip())
seqeunce = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [0] * n
for i in range(n):
dp[i] = seqeunce[i]
for i in range(1,n):
for j in range(i):
if seqeunce[i] > seqeunce[j]:
dp[i] = max(dp[i], dp[j]+seqeunce[i])
print(max(dp))
3. Learned
- dp 초기값을 어떻게 설정할 것인지 생각하자
- 했던 실수를 반복해서 하지 말자
No. 11504
1. Problem
2. My Solution
- 증가하는 부분 수열 부분과 감소하는 부분 수열을 나누어 판단해야 함
- dp[i][j] 에서 i = n, j 는 0과 1로 나누어 증가 부분과 감소부분을 저장
- 증가하는 수열의 끝에서 감소하는 수열이 시작하므로 dp[j][0], dp[j][1] 에서 큰 값을 이용
- ex) n = 11 일때
import sys
n = int(sys.stdin.readline().rstrip())
sequence = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [[1,1] for _ in range(n)]
result = 0
for i in range(1,n):
for j in range(i):
if sequence[i] > sequence[j]:
dp[i][0] = max(dp[i][0], dp[j][0]+1)
elif sequence[i] < sequence[j]:
dp[i][1] = max(dp[i][1], dp[j][0]+1, dp[j][1]+1)
for i in range(n):
if result < max(dp[i]):
result = max(dp[i])
print(result)
3. Others' Solutions
- 증가하는 부분 수열과 감소하는 부분 수열의 합이 가장 큰 부분수열을 구함
- 제일 마지막에 -1 을 통해 중복으로 계산된 횟수를 제거함
- 아래 예제에서는 원소 5까지 증가하는 부분 수열의 개수가 5개이고 원소 5부터 감소하는 부분 수열의 개수가 3이므로 3+5-1 = 7
