[ 알고리즘 ] Dynamic Programming : 돌 가져가기, LIS(longest Increasing Subsequence)

1. 돌 가져가기

 

n개의 돌이 있고, 각 돌에는 숫자가 있다.

게임 참가자는 두명이다. 

A는 하나의 타일 X를 고른다

B는 X를 기준으로 왼쪽 혹은 오른쪽 에서만 돌을 가져갈 수 있다. 

이가 반복된다. 

돌에 적힌 숫자가 점수가 된다. 

 

이 때 어떻게 하면 최고점이 보장 될 수 있을까?

 

1,1 idea  (모름)

 

2. longest Increasing Subsequence (LIS)

 

숫자의 나열이 있을때, 증가하는 가장 긴 Subsequence를 찾는 것이 이 문제의 정의이다. 

 

2.1 idea

 각 숫자의 나열에 나로 끝나는 LIS의 개수를 적는다

내가 앞 숫자가 나보다 작으면 내 앞 배열 + 1을 해주면 된다. 

8	2	7	6	3	4	1	2
1	1	2	2	2	3	1	2

 

2.2 Proof

 

여러가지 경우에도 이 규칙이 성립하는지 확인해보자

 

1) 길이가 같은 배열이 두개일 때

이 상황은 아래와 같이 세가지 경우로 나뉘게된다.

1. 앞에 숫자의 값이 뒤의 숫자의 값보다 작을 때  => 이 경우는 모순이 있다. 이 경우레는 뒤에 숫자의 길이가 앞에숫자 길이 +1이 되었을 것이다. 
2. 앞에 숫자의 값이 뒤의 숫자의 값과 같을 때  => 아무거나 해도 상관없다.
3. 앞에 숫자의 값이 뒤의 숫자의 값보다 클 때  => 더 작은 뒤의 값을 저장한다. 

2) 숫자가 같은 배열이 두개일때

이 상황도 아래와 같이 세가지 경우로 나눠진다.

1. 앞의 숫자의 길이가 뒤의 숫자의 길이보다 짧을 때  => 모순. 뒤에 숫자도 어딘가에서 +1해서 받아와야하는데 앞에랑 숫자가 같으므로 모순이다.
2. 앞의 숫자의 길이가 뒤의 숫자의 길이와 같을 때  => 규칙에 성립한다.
3. 앞의 숫자의 길이가 뒤의 숫자의 길이보다 길 때  => 모순. 뒤에 숫자도 어딘가에서 +1해서 받아와야하는데 앞에 길이보다 작은것은 모순이다.

(모름/0