N = int(input())
num = list(map(int, input().split()))
cnt = 1
max_ = num[0]
for i in range(1, N):
if num[i] > max_: # i번째 숫자를 i-1까지의 숫자 중 최댓값과 비교
cnt += 1 # 값이 증가하면 +1
max_ = num[i] # 최댓값 갱신
print(cnt)
예시 문제에 나오는 10 20 10 30 20 50 의 경우 정답 4가 아무런 문제 없이 출력된다.
그러나.... 1 100 101 2 3 4 5 와 같이 중간에 매우 큰 숫자가 나오면 그 다음 숫자에 대해서는 전혀 고려되지 않는 반례가 있어 틀렸다.
이 문제는 i번째 대소를 고려할 때, 0번째 부터 i-1번째까지 모든 숫자를 고려해야 한다. 즉, 이중 반복문으로 접근해야 한다.
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
number | 1 | 100 | 101 | 2 | 3 | 4 | 5 |
dp | 1 | 2 | 3 | 2 | 3 | 4 | 5 |
예를 들어 위 표에서 index 3의 숫자 2의 대소 비교는 index 0 ~ 2까지 1, 100, 101과 각각 비교 되어야 한다.
그리고 각 index의 숫자와 비교하여 큰 경우에만 counting 하여 dp에 그 값을 저장한다. 여기서는 index 0보다 크기 때문에 index0의 dp 인 1에 1을 더한 2를 저장한다.
이렇게 하면 중간에 매우 큰 숫자인 100, 101을 피하여 수열을 이어 나갈 수 있다.
코드로 구현하면 아래와 같다.
N = int(input())
number = list(map(int, input().split())
dp = [1 for _ in range(N)]
for i in range(N):
for j in range(i): # i번째 숫자와 대/소를 비교
if number[i] > number[j]:
# j번째 dp에 1을 더한 값과 j-1번째 dp에 1을 더한 값을 비교하여 더 큰 값을 저장
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))