[백준]동적 계획법1/가장 긴 증가하는 부분 수열/11053 풀이 JAVA
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은
A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 A(i)가 주어진다. (1 ≤ A(i) ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이(JAVA)
예제를 보면서 문제를 이해해 보자.(백준 예제)
아래와 같은 수열 A와 부분 수열의 길이인 dp 배열이 있다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| A | 10 | 20 | 10 | 30 | 20 | 50 |
| dp | 1 | 2 | 1 | 3 | 2 | 4 |
| 부분 수열 | {10} | {10, 20} | {10} | {10, 20, 30} | {10, 20} | {10, 20, 30, 40} |
dp[N]에 dp[0]부터 dp[N]까지 오름차순인 요소들의 갯수를 저장하는 방법이다.
다른 예제 하나 더
| index | 0 | 1 | 2 | 3 |
| A | 30 | 20 | 10 | 20 |
| dp | 1 | 1 | 1 | 2 |
| 부분 수열 | {30} | {20} | {10} | {10, 20} |
| import java.io.*; | |
| import java.util.StringTokenizer; | |
| public class Main { | |
| static int[] A; // 입력받을 스열 A | |
| static int[] dp;// 메모제이션 할 배열 dp | |
| // ex) dp[i] = m; : 0~i 요소 중 증가 수열 요소는 m개(최장 증가 부분 수열의 길이가 m) | |
| // 최장 증가 부분 수열 | |
| static int LTS(int N) { | |
| if (dp[N] == 0) { // 아직 초기화가 되어있지 않으면... | |
| dp[N] = 1; // 자기 자신의 원소(=1개)로 초기화 | |
| // 0 ~ N-1끼지의 요소를 N과 비교하며 최대 요소 갯수 찾기 | |
| for (int i = N - 1; i >= 0; i--) | |
| if (A[i] < A[N]) // A[i]의 값이 A[N]보다 값이 작으면 | |
| dp[N] = Math.max(dp[N], LTS(i) + 1); // dp[N]와 dp[i]+1의 값 중 최댓값으로 갱신 | |
| } | |
| return dp[N]; | |
| } | |
| public static void main(String[] args) throws IOException { | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| // 수열 A의 크기 입력 | |
| int N = Integer.parseInt(br.readLine()); | |
| A = new int[N]; | |
| dp = new int[N]; | |
| // 수열 A의 요소 입력 | |
| StringTokenizer st = new StringTokenizer(br.readLine()); | |
| for (int i = 0; i < N; i++) | |
| A[i] = Integer.parseInt(st.nextToken()); | |
| // dp[0] ~ dp[N - 1] 채우기 | |
| for (int i = 0; i < N; i++) | |
| LTS(i); | |
| // 최댓값 찾기 | |
| int max = dp[0]; | |
| for (int i = 1; i < N; i++) | |
| if (max < dp[i]) max = dp[i]; | |
| // 출력 | |
| System.out.println(max); | |
| } | |
| } |
여기부터는 내가 삽질한 부분이다.
궁금증 1
수열 A가 {3, 2, 1, 2}면
최대 증가 부분 수열은 {1, 2}의 2이다!
(dp는 {1, 1, 1, 2}가 된다.)
나는... {1, 2, 3}해서 3일 줄 알았는데
dp[0]부터 dp[N]까지 증가 부분 수열을 구해야하기 때문에 A[N]이상의 요소를 포함할 수 없다~~
그리고 위의 예제인 A = {10, 20, 10, 30, 20, 50}만 보고
오잉? 걍 for문 돌려서 큰 거 만나면 count++하는 식으로 한 담에 count 출력하면 되는 거 아냐?
이렇게...^^
int max = A[0];
int count = 1;
for (int i = 1; i < N; i++)
if (max < A[i]) {
max = A[i];
count++;
}
라고 생각했다가~ 틀렸다.
왜 틀렸냐면...
A={4, 1, 2, 3}같은 수열로 예를 들 수 있는데,
이때 dp는 {1, 1, 2, 3}이 된다.
그런데 저 코드대로 하면
max = 4가 되어서 count가 더이상 ++이 될 수 없다.
궁금증 2
dp[N] = Math.max(dp[N], LTS(i) + 1);을
dp[N] = LTS(i) + 1;이라고 해도 되지 않을까!? 였는데... 역시 안 된다.
dp[N] = LTS(i) + 1;라고 하면
A = {1, 2, 3, 2}에서
dp = {1, 2, 3, 1}이 되어야하는데,
LTS(2)떄 dp[2] = LTS(1) + 1 = 2가 되어버린다. 3이 되어야 하는데!!
(dp = {1, 2, 2, 2}가 되어버린다.)
그래서 꼭 현재 값보다 작아지지 않도록... 비교를 해주어야 한다.
궁금증 3
LTS(0 ~ N - 1)을 for문으로 돌리지 말고 어차피 재귀니까 LTS(N - 1)로 하면 안될까!?
안 된다!
A = {1, 2, 3, 1}을 예제로 들 수 있다.
dp = {1, 2, 3, 1}이 되어야하지만
dp = {0, 0, 0, 1}이 되어버린다.
왜냐하면 LTS(3)으로 시작하지만, A[3]보다 작은 것은 없기에 if문 안의 LTS재귀를 할 수가 없다!
참 많이도 궁금했지만 해결해서 기분이 좋다. 허리는 좀 아프지만....^^