3이라는 숫자가 최대값일 때, 포인터1에 3이라는 숫자의 인덱스값을 저장해주고, 다른 하나의 포인터2는 계속해서 오른쪽으로 나가며 포인터1의 숫자와 비교를 해준다. 만약 포인터2가 가리키는 숫자가 포인터1의 숫자보다 크다면 포인터1의 인덱스는 포인터2가 가르키는 인덱스로 갱신됨과 동시에 "1"이 더해져 밟을 수 있는 돌의 갯수를 계속해서 더하는 방식으로 진행할 수가 있다.
처음에 문제를 잘못 이해해서 투포인터를 사용하는 문제로 이해를 해버렸다. 알고보니 동적프로그래밍을 사용해서 푸는 문제였다.
4. 그렇게 i가 끝에 도달했을 무렵에는 각각의 돌에서 시작했을 경우의 최대 스텝수가 리스트에 담기게 되는데,
5. 그 최대 스텝수의 리스트의 최대값을 출력해주면 결국 밟을 수 있는 돌의 최대 갯수가 된다.
이를 코드로 작성하면 아래와 같다.
코드
import sys
# 입력값 받아들이기
N = int(sys.stdin.readline()) # 돌의 갯수
stones = list(map(int, sys.stdin.readline().split())) # 돌의 높이로 이루어진 리스트
dyn = [1]*N # 동적프로그래밍을 위한 테이블 준비
# 현재의 돌 i
for i in range(1,N):
# i 이전의 돌을 밟는 경우를 시뮬레이션 돌려보는데,
for j in range(i):
# 만약 현재의 돌의 높이가 시뮬레이션에서의 돌의 높이보다 높을 경우
if (stones[i] > stones[j]):
# "현재의 돌의 스텝수"와 "이전의 돌들을 밟고 현재의 돌을 밟을 경우의 스텝수 + 1" 중 최대값으로 갱신해준다.
dyn[i] = max(dyn[i], dyn[j]+1)
# 밟을 수 있는 돌의 갯수 출력
print(max(dyn))
