테스트케이스를 만들어보다가 깨달았다…ㅠㅠㅠㅠ
DP에 LIS인데, LIS가 2차원이라고 하더라도 똑같은 로직을 따라가면 된다.
이 문제에서 일단 ‘최소거리’로 간다고 했으므로 항상 오른쪽 아래로 가는 방식이다.
그래서 그냥 이 그림으로 쉽게 살펴보자.
노란색으로 동그라미 친 곳의 LIS를 살펴보고 싶다면
파란색 박스를 다 살폈을 때, 노란색 박스가 그 특정 박스보다 크다면 그 특정 박스의 LIS+1과 현재 LIS값을 살피고 갱신해주면 된다 자세한 건 코드에서 확인 가능
그리고 마지막 출력이 중요하다.
마지막 temp[N-1][N-1]을 출력한다고 계속 생각하다보니까 헤맸는데, 그냥 해당 temp 배열에서 가장 큰 값을 가져오면 그게 가장 긴 LIS이다.
import sys
input=sys.stdin.readline
N=int(input())
List=[list(map(int,input().split())) for _ in range(N)]
temp=[[1 for _ in range(N)] for _ in range(N)]
check=[[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(i+1):
for l in range(j+1):
if List[k][l]<List[i][j]:
temp[i][j]=max(temp[i][j],temp[k][l]+1)
# print(temp)
ans=0
for i in temp:
for j in i:
if j>ans: ans=j
print(ans)
''''
테스트케이스
5
1 2 3 4 5
2 3 4 5 6
6 5 4 3 2
5 4 3 2 1
4 3 2 1 8
7
1 3
3 1
2
'''반성..<
편견 가지고 보지말자..!! LIS의 특징을 잘 생각하자
