[DP] Softeer(소프티어) level 3 징검다리 Java 풀이 (+ 테스트 케이스)

https://softeer.ai/practice/6293

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

문제 풀이법

1. 돌 높이를 저장하는 배열과, 각각의 돌에 도달하기 위한 걸음 수를 저장하는 DP 테이블 생성(이때 DP 테이블 값은 모두 1로 초기화)
2. for 루프를 돌며 이전 인덱스의 돌 높이보다 현재 돌 높이가 더 높을때 DP[현재 인덱스] = max(현재 인덱스 DP 테이블, 이전 인덱스 DP 테이블에 + 1) 적용
3. DP 테이블에서 가장 큰 값 리턴

예를 들어

6
1 7 8 2 3 4

의 경우, 잘못된 구현을 하면 1 7 8만 따져서 3이 되겠지만 정답은 1 2 3 4인 4가 정답이다.

즉 각 돌에 도달하기 위한 모든 걸음 수를 검사해야함

 

결과적으로 돌 높이를 저장하는 배열은 다음과 같겠고,

0	1	2	3	4	5
1	7	8	2	3	4

DP 테이블은 다음과 같을 것 이다.

0	1	2	3	4	5
1	2	3	2	3	4

7의 경우 1이 자신보다 낮으므로 DP테이블에서 max(dp[1], dp[0] + 1)이 적용될테고 

8의 경우 1과 7 모두 자신보다 낮으므로, DP 테이블에서 max(dp[2], dp[0] + 1), max(dp[2], dp[1] + 1) 두 번 연산하여 3이 저장된다.

 

이런식으로 모든 DP 테이블을 채워나가고 결과적으로 가장 큰 값을 리턴하면 정답.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int numOfStone = Integer.parseInt(st.nextToken());
        int[] stoneList = new int[numOfStone];
        int[] stepTable = new int[numOfStone];
        st = new StringTokenizer(in.readLine());
        for(int i = 0; i < numOfStone; i++){
            stoneList[i] = Integer.parseInt(st.nextToken());
            stepTable[i] = 1;
        }

        for(int j = 1; j < numOfStone; j++){
            for(int k = 0; k < j; k++){
                if(stoneList[j] > stoneList[k]){
                    stepTable[j] = Math.max(stepTable[j], stepTable[k] + 1);
                }
            }
        }
        int answer = 0;
        for(int l = 0; l < numOfStone; l++){
            answer = Math.max(answer, stepTable[l]);
        }
        System.out.println(answer);
    }
}

 

참고 자료

https://youtu.be/egMtFlkH8LQ?si=k0GT6JdPe_EpoXY5