[소프티어] 징검다리 레벨3 자바 풀이 DP알고리즘

[소프티어] 징검다리 레벨3 자바 풀이 DP알고리즘

 

 

DP문제는 어려운데 재밌다.

급한대로 보카 영단어책에 마구 적어봤다.

 

역시 디피야 디피

레벨3 체감중...

 

 

 

 

 

링크

https://softeer.ai/practice/6293/history?questionType=ALGORITHM

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

 

 

 

문제스펙

 

 

미리보는 해설

A돌에서 B돌로 움직일때처럼

1칸 1칸 움직이는 경우에

최대값을 dp배열에 저장했다.

 

2~n 번째 돌을 반복문돌리면서

1~n-1 번째 돌에 대해서 하나하나씩 최대값 비교.

 

 

정답 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int cost[] = new int[n];
        int dp[] = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            int tempCost = Integer.parseInt(st.nextToken());
            cost[i] = tempCost;
            dp[i] = 1;
        }

        int dap = 1;
        for(int i=1; i<n; i++){ // 신규 돌
            for(int j=0; j<i; j++){ // 과거 되돌아보기
                //System.out.println("\n\ni,j="+i+","+j);
                //System.out.println("cost="+cost[j]+"<"+cost[i]);
                if(cost[j] < cost[i]){ // 과거 돌보다 < 신규로 밟는 돌이 높을때, 1만큼 점프 가능한데
                    // 신규 돌의 dp값과 vs 과거 돌의 dp값 + 1점프한값, 비교해서 더 높은 값을, 현재의 신규 돌의 dp값 저장
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            // 현재의 신규 돌의 dp값의 최대가치가 정해지면서 계속 max값 찾기
            dap = Math.max(dap, dp[i]);
        }
        
        // bw.write(String.valueOf(ff)+"\n");
        bw.write(String.valueOf(dap));
        bw.close();
    }
}