[소프티어] 징검다리

https://softeer.ai/practice/6293

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

 

왠지 문제가 너무 쉽다 했는데, 문제를 잘못 이해했다. 

첫번째 다리를 무조건 지나야하는 줄 알았는데, 어느 곳을 밟더라도 상관 없는 문제였음. 

이런 것이 바로 DP 문제 ! 

 

문제에 접근할 때, 각자의 돌을 밟았을 경우 최대 몇개를 밟을 수 있는지 순서대로 계산해준다.

다 계산이 되었다면, 그 중 최댓값을 출력해주면 된다. 

 

처음에 잘못 이해하고 푼 코드

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

public class Main {

    public static void main(String[] args) throws IOException{

        // 반복해서 수 받으면서 '직전에 밟은 돌' 보다 크면 1. 돌 정보 업데이트 2. count++

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int num = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int current = Integer.parseInt(st.nextToken());
        int count = 1;

        for (int i = 1; i < num; i++){
            int next = Integer.parseInt(st.nextToken());

            if (next > current){
                current = next;
                count++;
            }
        }

        System.out.println(count);

    }
}

 

다시 DP로 푼 코드

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

public class Main {

    public static void main(String[] args) throws IOException{
        // (1) 시간 복잡도 : 보통 컴퓨터는 1초당 10^8 정도 처리할 수 있음
            // 문제 조건은 2초이기 때문에 2*10^8까지 가능하고,
            // 입력되는 수는 3*10^3 이기 때문에 넉넉하게 O(N^2) 까지 가능하다. 

        // (2) 해당 문제는 어느 돌을 첫번째로 밟든, 최대한 돌을 많이 밟으면 되기 때문에, 
            // 각자의 돌을 마지막으로 밟았을 때, 최대 몇 개 밟을 수 있는지 계산하기.
            // 즉, 앞에서부터 계속 반복문으로 비교하면서 계산한다. 
            // 최종으로는 구한 수 중에 가장 큰 수 print

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int arr[] = new int[N];
        
        // dp[i] 배열은 i번째 돌을 마지막으로 밟았을 때, 밟을 수 있는 돌의 최대 개수를 저장
        int dp[] = new int[N];
        Arrays.fill(dp, 1); //모든 돌은 최소 자기 자신 하나만 밟을 수 있으므로 dp 배열을 1로 초기화
        
        st = new StringTokenizer(br.readLine());

        // 입력 값을 배열에 입력하기
        for (int i = 0; i < N; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        // (2) 돌아가면서 값 비교하기 -> 이전 돌보다 다음 돌이 크면, 비교해서 큰 수로 업데이트해주기

        for (int i = 0; i < N; i++){
            for (int j = 0; j < i; j++){
                if (arr[i] > arr[j]){ // 다음 돌이 더 크면?
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 이전돌 밟고 현재돌 밟기or 현재돌 중에 큰 수 담기
                }
            }
        }

        Arrays.sort(dp);

        System.out.println(dp[N-1]);
        
    }
}

---

Reference

 

https://velog.io/@beneficial/%EC%86%8C%ED%94%84%ED%8B%B0%EC%96%B4%EC%9E%90%EB%B0%94-lv3.-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC

[소프티어/자바] lv3. 징검다리