[๋ฐฑ์ค€/C++] 11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด

2022. 7. 20. 22:44ยทPS/C++
๋ชฉ์ฐจ
  1. ๐Ÿค”๋ฌธ์ œ ์ดํ•ด
  2. ๐Ÿ’ก์ฒซ๋ฒˆ์งธ ์•„์ด๋””์–ด
  3. ๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ
  4. โŒํŠธ๋Ÿฌ๋ธ” ์ŠˆํŒ…
728x90

๋ฐฑ์ค€
11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด


๐Ÿค”๋ฌธ์ œ ์ดํ•ด

์–ด๋А ํ•œ ์ˆซ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ์—๋Š” ๊ฐ์†Œํ•˜๋Š” ์ˆซ์ž๋“ค์ด, ์˜ค๋ฅธ์ชฝ์—๋Š” ์ฆ๊ฐ€ํ•˜๋Š” ์ˆซ์ž๋“ค์ด ์˜ค๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์ฐพ๋Š” ๋ฌธ์ œ์ด๋‹ค.

์ด๋•Œ, ๊ฐ™์€ ์ˆซ์ž๊ฐ€ ์—ฐ์†์ ์œผ๋กœ ๋‚˜์˜ฌ ์ˆ˜ ์—†๋‹ค.


๐Ÿ’ก์ฒซ๋ฒˆ์งธ ์•„์ด๋””์–ด

๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ์‘์šฉ ๋ฒ„์ „์ด์—ˆ๋‹ค. 

 

๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ

dp_in[i]๋Š” i๋ฒˆ์งธ ์ˆ˜๋ฅผ ๋งˆ์ง€๋ง‰ ์ˆ˜๋กœ ํ–ˆ์„ ๋•Œ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๊ณ ,

dp_de[i]๋Š” i๋ฒˆ์งธ ์ˆ˜๋ฅผ ์ฒซ๋ฒˆ์งธ ์ˆ˜๋กœ ํ–ˆ์„ ๋•Œ ๊ฐ์†Œํ•˜๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

 

1. dp_in๊ณผ dp_de๋Š” ๋ชจ๋‘ 1๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.

2. ์•ž์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํ˜„์žฌ ์ˆซ์ž๊ฐ€ ๋‹ค์Œ ์ˆซ์ž๋ณด๋‹ค ํฌ๋‹ค๋ฉด, ํ˜„์žฌ dp_in๊ณผ ์ด์ „๊ฐ’ dp_in์— 1์„ ๋”ํ•œ ๊ฐ’ ์ค‘์—์„œ ๋” ํฐ ๊ฐ’์„ dp_in์˜ ํ˜„์žฌ๊ฐ’์— ๋„ฃ์–ด์ค€๋‹ค.

3. ๋’ค์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ํ˜„์žฌ ์ˆซ์ž๊ฐ€ ๋‹ค์Œ ์ˆซ์ž๋ณด๋‹ค ํฌ๋‹ค๋ฉด, ํ˜„์žฌ dp_de์™€ ์ด์ „๊ฐ’ dp_de์— 1์„ ๋”ํ•œ ๊ฐ’ ์ค‘์—์„œ ๋” ํฐ ๊ฐ’์„ dp_de์˜ ํ˜„์žฌ๊ฐ’์— ๋„ฃ์–ด์ค€๋‹ค.

4. dp_in๊ณผ dp_de์˜ i๋ฒˆ์งธ ์ˆ˜๋Š” ๊ฒน์น˜๋ฏ€๋กœ dp_in๊ณผ dp_de๋ฅผ ๋”ํ•˜๊ณ  1์„ ๋นผ์ค€ ๊ฐ’๋“ค์„ ๋น„๊ตํ•ด์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

โŒํŠธ๋Ÿฌ๋ธ” ์ŠˆํŒ…

์œ„ ํ’€์ด์—์„œ์˜ 4๋ฒˆ์—์„œ dp_in + dp_de๋ฅผ ํ•ด์ค„ ๋•Œ ๊ฒน์น˜๋Š” ๊ฐ’ 1์„ ๋นผ์ฃผ์ง€ ์•Š์•„์„œ ํ‹€๋ ธ์—ˆ๋‹ค.


#include <iostream>
#include <cmath>

using namespace std;

int dp_in[1001];
int dp_de[1001];
int arr[1001];
int n;

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

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

    for (int i = 0; i < n; i++) {
        dp_in[i] = 1;
        dp_de[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp_in[i] = max(dp_in[i], dp_in[j] + 1);
            }
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= i; j--) {
            if (arr[j] < arr[i]) {
                dp_de[i] = max(dp_de[i], dp_de[j] + 1);
            }
        }
    }

    int result = dp_in[0] + dp_de[0] - 1;
    for (int i = 1; i < n; i++) {
        int tmp = dp_in[i] + dp_de[i] - 1;
        if (result < tmp) result = tmp;
    }
    cout << result;
}
728x90

'PS > C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€/C++] 1766๋ฒˆ ๋ฌธ์ œ์ง‘  (0) 2022.07.21
[๋ฐฑ์ค€/C++] 13398๋ฒˆ ์—ฐ์†ํ•ฉ 2  (0) 2022.07.20
[๋ฐฑ์ค€/C++] 11053๋ฒˆ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด  (0) 2022.07.20
[๋ฐฑ์ค€/C++] 5021๋ฒˆ ์™•์œ„๊ณ„์Šน  (0) 2022.07.18
[๋ฐฑ์ค€/C++] 11057๋ฒˆ ์˜ค๋ฅด๋ง‰ ์ˆ˜  (0) 2022.07.18
  1. ๐Ÿค”๋ฌธ์ œ ์ดํ•ด
  2. ๐Ÿ’ก์ฒซ๋ฒˆ์งธ ์•„์ด๋””์–ด
  3. ๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ
  4. โŒํŠธ๋Ÿฌ๋ธ” ์ŠˆํŒ…
'PS/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€/C++] 1766๋ฒˆ ๋ฌธ์ œ์ง‘
  • [๋ฐฑ์ค€/C++] 13398๋ฒˆ ์—ฐ์†ํ•ฉ 2
  • [๋ฐฑ์ค€/C++] 11053๋ฒˆ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด
  • [๋ฐฑ์ค€/C++] 5021๋ฒˆ ์™•์œ„๊ณ„์Šน
yulee_to
yulee_to
  • yulee_to
    yulee
    yulee_to
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (150)
      • CS (2)
        • OS (0)
        • DB (0)
        • Network (2)
      • Develop (21)
        • Spring (9)
        • Java (12)
        • Python (0)
        • Algorithm (0)
        • ๊ธฐํƒ€ (0)
      • PS (39)
        • C++ (39)
        • Java (0)
      • TIL (43)
      • Book (39)
        • ์ž๋ฐ”์˜ ์‹  (32)
        • ์Šคํ”„๋ง ์ž…๋ฌธ์„ ์œ„ํ•œ ์ž๋ฐ” ๊ฐ์ฒด ์ง€ํ–ฅ์˜ ์›๋ฆฌ์™€ ์ดํ•ด (7)
      • ETC (4)
        • Blog (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ๋ฉ€ํ‹ฐ์บ ํผ์Šคit๋ถ€ํŠธ์บ ํ”„
    EC2
    aws
    boj
    ๋ฐฑ์ค€
    1์ผ1๋ฐฑ์ค€
    ์—์Šค๋„ท์‹œ์Šคํ…œ ๋ถ€ํŠธ์บ ํ”„
    ํด๋ผ์šฐ๋“œ ํ™œ์šฉ ๋„คํŠธ์›Œํฌ ์—”์ง€๋‹ˆ์–ด ๋ถ€ํŠธ์บ ํ”„
    ๊ฐ์ฒด์ง€ํ–ฅ
    ์—์Šค๋„ท์‹œ์Šคํ…œ
    ์ž๋ฐ”์˜ ์‹ 
    ์•Œ๊ณ ๋ฆฌ์ฆ˜
    C++
    GodOfJava
    ์Šคํ”„๋ง ์ž…๋ฌธ
    TiL
    Java
    ๋ถ€ํŠธ์บ ํ”„ํ›„๊ธฐ
    ์Šคํ„ฐ๋””
    ์ž๋ฐ”
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
yulee_to
[๋ฐฑ์ค€/C++] 11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด

๊ฐœ์ธ์ •๋ณด

  • ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ
  • ํฌ๋Ÿผ
  • ๋กœ๊ทธ์ธ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.