징검다리

작성일: 2024-11-01

문제 링크 : https://softeer.ai/practice/6293

접근 방식

소프티어의 특정 문제같은 경우, 문제가 뜻하는바가 무엇인지 이해가 잘 안되는 경우가 있었다.

이 문제가 나에게 그러해서, 이해를 못했었다.

문제는 이러했다.
왼쪽부터 오른쪽까지 일정 높이를 가진 돌이 주어진다.
나는 무조건 이전에 올랐던 돌보다 높았던 돌만 오를 수 있다.
이 경우에, 내가 오른 돌의 최대 개수를 구해야 한다.
1 2 3 2 1 과 같이 주어진다면
1 => 1 2 3 (3개)
2 => 2 3 (2개)
3 => 3 (1개) 2 => 2 (1개) 1 => 1 (1개)
와 같이 오를 수 있다. 나는 총 세 개의 돌을 오를 수 있는 것이다.

따라서 특정 계단에서 오를 수 있는 계단의 최대 숫자가 결과 값이 된다.

이는 DP와도 연관됨을 알 수 있다.
내가 현재 위치가 3이라고 했을 때, 2까지의 횟수와 3까지의 횟수를 비교해서 큰 수가 3까지왔을 떄의 최대 개수가 된다.

결과

소스 코드

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[] = new int[N];
        for(int i=0; i<N; i++) arr[i] = sc.nextInt();
        int answer = 0;
        int dp[] = new int[N];
        for(int i=0; i<N; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if(arr[j]<arr[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            answer = Math.max(dp[i], answer);
        }
        System.out.println(answer);
    }
}

현재 돌 위치에 서면 오른 것으로 판단하고 1을 부여한다.

이후에 현재 위치 전까지 완전 탐색을 통해, 오를 수 있는 수를 비교하고 현재의 개수와 이전개수와 비교하여 최대 값을 갱신한다.

여기서 이전 개수에 +1을 하는 이유는, 계단을 올랐기 때문에 오른 계단을 표시해주는 것이다.

알게 된 점

없음.