[ Baekjoon - 11/21 ] - 11722번: 가장 긴 감소하는 부분 수열

문제 링크 : https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

소요 시간 : 1시간

가장 긴 감소하는 부분 수열 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	25576	16155	13152	64.165%

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

  1    >   N (수열 A의 크기, N : [1, 1000]) 

  2   >  Ai (Ai 값 : [1, 1,000]) 

출력 > 수열 A의 가장 긴 감소하는 부분 수열의 길이

 

 

▶ 문제

N개의 값으로 이루어진 수열 A가 주어졌을때, 가장 긴 감소하는 부분 수열의 길이를 출력

 

 

▶ 시간, 메모리 제한 :1초, 256MB

 

2.  문제를 익숙한 용어로 재정의와 추상화

문제가 직설적으로 잘 표현되어 있어서 그려보지 않았음

 

3.  문제 해결 방안

1st 접근 ) dp

dp를 사용하는 큰 이유는 중복을 줄이기 위함인데,

여기서는 큰 숫자가 앞에 있으면, 뒤의 작은 숫자는 최대의 긴 수열을 선택할 때 앞의 큰 숫자를 꼭 선택하게 될 것이기 때문이다. 

입출력 예제로 설명해보면

[10, 30, 10, 20, 20, 10]의 경우, 30 뒤에 있는 10, 20, 20, 10은 최장 감소 수열을 선택할때 꼭 30을 선택한다.

 

위 문제는 최장 감소 부분수열의 길이를 출력해야하므로, dp의 각 값은 현재까지의 최장감소부분수열의 길이가 될 것이다.

이제 "현재"의 기준을 잡아야하는데, 위 표처럼 그려보니 마지막 부터 접근이 편할 것 같아서

< dp[i] = 마지막부터 i까지 가능한 부분 수열의 길이 >로 정의하기로 했음. 

=> 앞에서부터 저장하든, 뒤에서부터 저장하든 상관없는 문제이긴하다.

 

뒤에서부터 앞으로 진행하면서  dp의 값을 갱신하는데, 뒤 배열에 현재 값 보다 작은 값이 있다면 dp[뒤의 값]과 dp[현재 값]+1 중 최댓값으로 저장해주면 된다.

 

4.  위 계획 검증

큰 숫자가 앞에 있으면, 뒤의 작은 숫자는 최대의 긴 수열을 선택할 때 앞의 큰 숫자를 꼭 선택한다.

조금 당연한 말이라 더 이상의 검증은 언어의 한계로...

 

5.  코드 작성

▶ Java 11 ( 36468KB, 440ms)

import java.util.*;
import java.io.*;

public class Main{
    static int M,N;
    static int[][] map, dp;
    static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            for (int n = 0; n < N; n++) {
                map[m][n] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new int[M][N];
        dp[0][0] = 1;
        BFS();
        
        bw.write(dp[M-1][N-1]+"\n");
        bw.flush();
    }

    private static void BFS() {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(0,0, map[0][0]));

        while (!pq.isEmpty()){
            Point node = pq.poll();
            if(node.x==M-1 && node.y==N-1) {
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                // 맵밖, 값이 작은가
                if(0<=nx && nx<M && 0<=ny && ny<N && map[nx][ny] < map[node.x][node.y]){
                    if(dp[nx][ny]==0)
                        pq.add(new Point(nx,ny,map[nx][ny]));
                    dp[nx][ny] += dp[node.x][node.y];

                }
            }
        }
    }
}

class Point implements Comparable<Point>{
    int x,y,height;

    public Point(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.height = height;
    }

    @Override
    public int compareTo(Point o) {
        // 높이 순으로 내림차순, 큰 높이부터 처리를 해주어야 중복방문 막기 가능
        return o.height - height;
    }

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                ", height=" + height +
                '}';
    }
}

 

6.  결과

 

7.  회고

당연히 맞을거라 생각해 제출한 답안이 2번이나 틀렸는데.. 그 이유는 입출력의 가장 최솟값을 고려하지 않아서였다. 

 

첫번째는 dp의 초기 값을 0으로 설정했기 때문에, 

아무리 수열이 없다 해도 본인 만을 포함한 수열(길이 1)이 도출될 수 있으므로 초기 값을 넣어줘야 했다.

 

두번째는 N이 1, 수열도 1만 들어올 경우 오류였다.

배열에서 초기 값을 정해줬을지라도 N이 1이면 for문으로 들어오지 않아, 기존 초기 값에 따른 ans가 0이 출력 되므로.

 

제출 전에 가장 첫값 정도는 돌려보는 습관을 길러야겠음. 후