SWEA[3307] - 최장 증가 부분 수열[D3]

링크

SWEA[3307]

문제설명

• 최장 증가 부분 수열[D3]

문제풀이

• int[] arr = {1,3,2,5,4}일 때,
• int[] len = {1,1,1,1,1}에서 시작
  • len[n]은 n번째 수의 수열의 길이
  • 각각의 수가 수열의 출발일 수 있으니 1로 초기화
• Update방법
  • len[1]의 경우 arr[1]과 이전 수인 arr[0]와 비교하여 arr[0]<arr[1]일 경우 len[0]+1을 업데이트한다
  • 이 때, 업데이트를 할 때는 최대값을 할당한다.
  • len[n]의 경우 arr[n]과 이전 수인 arr[i](i : 0~n-1)를 비교하여 arr[i]<arr[n]일 경우 len[i]+1이 최대값일 때, 업데이트 한다.
  • len[n] = max(len[n],len[i]+1) if arr[i]<arr[n]

문제코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class d3_3307 {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("res/3307.txt"));
        Scanner sc = new Scanner(System.in);
        int T=sc.nextInt();
        int ans=0;
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i]=sc.nextInt();
            }

            int[] mem = new int[N];
//            mem[n] = 수열의 길이
            for (int i = 0; i < N; i++) {
                mem[i]=1;
                for (int j = 0; j < i; j++) {
                    if(arr[i]>arr[j]) {    //연결 가능할 경우
                        mem[i] = Math.max(mem[i], mem[j]+1);
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                ans = Math.max(ans, mem[i]);
            }

            System.out.println("#"+test_case+" "+ans);
//            초기화
            ans=0;
        }
    }
}

아쉬운점

• 문제 이해를 제대로 못했었음.
• DP를 몰라서 겁먹고 시작했음.
• if(arr[i]>arr[j]) //연결 가능할 경우에서 인덱스 연결을 잘못해서 실수했음.(최장 감소 수열 나왔었음)

잘한점

• 일단 주먹구구식으로 직접 해보면서 규칙성을 찾았음.