백준 21600번 [계단](C++)-yes6686- 티스토리

백준 문제 풀이: 21600 [계단]

---

문제 링크: https://www.acmicpc.net/problem/21600

문제 설명:

주어진 배열에서 "계단"의 정의를 만족하는 가장 긴 부분 배열의 길이를 구하는 문제입니다. 계단의 정의는 다음과 같습니다:

• 각 원소는 이전 원소보다 작거나 같아야 하며, 동시에 각 원소는 해당 계단에서 선택 가능한 최대 높이를 넘지 않아야 합니다.

입력:

• 첫째 줄에 배열의 길이 n이 주어집니다. (1 ≤ n ≤ 100,000)
• 둘째 줄에 길이 n의 정수 배열 arr가 주어집니다. (1 ≤ arr[i] ≤ 100,000)

출력:

• 계단의 정의를 만족하는 가장 긴 부분 배열의 길이를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];
int dp[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    dp[0] = 1; // 첫 번째 계단의 길이는 1
    int maxLength = 1;

    for (int i = 1; i < n; i++) {
        if (arr[i] > dp[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        } else {
            dp[i] = arr[i];
        }
        maxLength = max(maxLength, dp[i]);
    }

    cout << maxLength << '\n';

    return 0;
}

예제

입력:
8
2 2 3 3 3 4 4 4

출력:
5

입력:
5
1 2 2 1 1

출력:
3

---

코드 설명

• DP 배열:
  • dp[i]는 i번째 계단까지의 최대 계단 길이를 저장합니다.
• 상태 전이:
  • 현재 값 arr[i]가 이전 값 dp[i-1]보다 크면 계단을 연장합니다.
  • 그렇지 않으면 계단의 길이를 현재 값 arr[i]로 초기화합니다.

시간 복잡도

• 배열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.
• 공간 복잡도는 O(n)입니다.

---

결과

코드는 입력된 배열에서 가장 긴 계단 길이를 정확히 계산하며, DP를 활용해 효율적으로 구현되었습니다. 문제의 제약 조건 내에서 잘 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!