[자바] 백준 11053 가장 긴 증가하는 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

풀이방법은,

 

{10, 20, 10, 30, 20, 50} 일 때

 

10

10 20

10 20 30 

10 20 50

10 20 30 50 

 

이렇게 이전에 갔던 길을 저장하고 있는 것이다.

 

처음에 재귀로 풀었다가 시간초과가 났다. 재귀도 결국 이전에 계산 했던 값을 가지고 들어가는 거니까 상관없을 거라 생각했는데 3중 포문이 되었다.

 

따라서 메모이제이션으로 푸는게 답이고 갔던 길의 수열 수를 저장하고 있는다.

 

1

1

1

1

1

1

 

로 시작해서 인덱스 0>1, 0>3, 0>4, 0>5로 갈 수 있으니까 ++한다. 

이 때, 기존의 수열 수가 더 많으면 그게 답에 더 가까우니까 ++하지 않는다.

 

1

2

1

2

2

2

 

1>3, 1>5로 갈 수 있으므로 ++한다.

이 때도 기존의 수열 수와 비교한다. 

 

1

2

1

3

2

3

 

2>3, 2>4, 2>5로 갈 수 있다.

이 때, 2>3으로 가려고 했는데 3에는 이미 3이라는 숫자가 있다. 2에는 1이라는 숫자가 있다. 2에 있는 2보다 3이라는 숫자가 더 크므로 그게 더 답에 가깝다.

 

1

2

1

3

2

3

 

이런 식으로 for문을 돌면서 계산해준다.

 

https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/baekjoon/P_11053.java

mychum1/shelf