[백준 알고리즘] (DP) 11053번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

백준 알고리즘 11053번

 

<첫 번째 오답 풀이>

DP문제라는걸 알고 접근했음에도 불구하고 이게 왜 DP로 풀어야되는지 헷갈렸다.

 

package dp;
 
import java.util.Scanner;
 
public class N11053 {
 
    static int array[];
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        array = new int[n];
        
        for(int i=0; i<n; i++) {
            array[i] = sc.nextInt();
        }
        sc.close();
        int temp=0;
        int max=0;
        
        for(int i=0; i<n; i++) {
            if(max<array[i]) {
                temp++;
                max= array[i];
            }
        }
        System.out.println(temp);
    }
 
}

 

나는 24라인~26라인이 조금 헷갈렸는데
24라인의 경우, j가 증가하면서 차례대로 앞에서부터 array[i]와 비교하는건 알겠는데,
dp[i]와 dp[j]는 왜 비교하는건지 궁금했다.

이는 이러한 경우 때문이다.
주어진 예제입력 {10, 20, 10, 30, 20, 50}을 보면,

잘라서 30까지만 봐도 24라인에서 만약 dp간의 비교조건이 없다면 i=4이고,  j=3인 경우에,
25라인 dp[4]는 dp[3]+1이 적용되어 dp[4]에 2가 들어간다.
따라서 Array[i], Array[j] 비교만아니라 dp[i], dp[j]도 함께 비교해주는 것이다.

또한, 참고한 분의 풀이에서는 Array[i] = Array[j]일때, dp도 같게 해주는데,
그 부분은 없어도 문제 없이 돌아간다.
(궁금해서 왜 있는지 반례 찾아보다가 빼고 제출해봤는데 정답 받음!)

 

 

 

Github: https://github.com/jaeuk9407/AlgorithmBOJ

jaeuk9407/AlgorithmBOJ