[Softeer/Java] 6293. 징검다리

[Softeer/Java] 6293. 징검다리

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

---

문제 해석

남북으로 흐르는 개울에 서쪽에서 동쪽으로 높이가 다른 돌들이 일렬로 놓여 있다. 이때, 철수는 서쪽에서 시작하여 동쪽으로 갈 때, 높이가 점점 증가하는 순서로만 돌을 밟고 건너가려고 한다. 주어진 돌의 높이에 따라 철수가 밟을 수 있는 돌의 최대 개수를 구하는 문제이다.

풀이 과정

문제는 "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)" 문제의 일종이다. 주어진 수열에서 가능한 한 길게 증가하는 부분 수열을 찾아야 한다.

이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming)을 사용하였다. dp[i]는 i번째 돌까지 고려했을 때 밟을 수 있는 돌의 최대 개수를 나타낸다. 초기에 모든 dp[i] 값을 1로 설정한다. 이후, 각 돌에 대해 이전의 모든 돌을 검사하여 현재 돌보다 낮은 돌에서 시작하는 부분 수열의 길이를 업데이트한다.

모든 돌을 검사한 후, dp 배열에서 가장 큰 값을 찾으면 그 값이 철수가 밟을 수 있는 돌의 최대 개수이다.

코드

package edu.ssafy.im.SOF.No6293;

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

public class Main {
    private static int N;  // 돌의 개수
    private static int[] A;  // 돌의 높이

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());  // 돌의 개수 입력

        A = new int[N];  // 돌의 높이를 저장할 배열

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());  // 돌의 높이 입력
        }

        sb.append(sol());  // 최대 돌 개수를 계산하는 함수 호출
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        int[] dp = new int[N];  // dp 배열 초기화
        Arrays.fill(dp, 1);  // 모든 위치의 초기 값은 1

        for (int i=0; i<N; i++) {
            for (int j=0; j<i; j++) {
                if (A[i] > A[j]) {  // 현재 돌이 이전 돌보다 높은 경우
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // dp 값을 업데이트
                }
            }
        }

        int ans = 0;  // 최대 개수 저장 변수
        for (int i=0; i<N; i++) {
            ans = Math.max(ans, dp[i]);  // dp 배열에서 최대값 찾기
        }

        return ans;  // 최대 개수 반환
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 𝑂(𝑁2)이다. 모든 쌍의 돌들을 비교하기 때문에, 돌의 개수가 최대 3000인 경우에도 계산 가능하다.

느낀점

이 문제를 통해 가장 긴 증가하는 부분 수열을 찾는 기본적인 방법인 동적 프로그래밍 기법을 활용하는 방법을 다시 한번 익힐 수 있었다. 또한, 이런 유형의 문제를 해결하는 데 있어서 더 효율적인 알고리즘을 공부할 필요성을 느낀다.

.