[Softeer/DP] 징검다리

문제

https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

해결방법

해당 문제는 DP문제로 점화식을 세우는것이 중요한 문제이다. 내가 생각한 점화식은 다음과 같다.

• 현재 높이보다 낮은 칸들의 최대값 + 1

문제를 풀고 다른 사람들의 풀이법을 보니 나와 조금 달랐다. 다른 사람들은 이 문제를 최장증가부분수열 해결 방법으로, dp[]에 해당 칸을 밟았을때와 안 밟았을때의 max값을 저장하는 방식으로 dp를 구현하였다.

 

그리고 내 해결방법의 오류나 단점을 생각해보면 다음과 같다.

• 메모리 문제
  • 실제로 입력조건에 맞춰 int[100000001]로 배열을 선언하였더니 메모리초과가 발생하여 Map으로 변경하였다.
• 시간복잡도
  • 다른 사람들의 풀이는 O(N)이지만, 나의 풀이는 Max값을 찾는 과정에 의해 O(N * 높이 고유 숫자 갯수)가 된다.

소스코드

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

public class Main {
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] rocks = new int[N + 1];
        Map<Integer, Integer> dp = new HashMap<>();
        String[] line = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            rocks[i] = Integer.parseInt(line[i]);
            dp.put(rocks[i], 0);
        }

        Set<Integer> keySet = dp.keySet();
        for(int i = 0; i < N; i++){
            int max = 0;
            for(Integer k : keySet){
                if(k > rocks[i])
                    continue;
                int v = dp.get(k);
                if(v > max)
                    max = v;
            }

            dp.replace(rocks[i], max + 1);
        }

        System.out.println(dp.values().stream().max(Comparator.naturalOrder()).orElse(0));
    }
}