[๋ฐฑ์ค€/C++] 12015๋ฒˆ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด 2

2022. 11. 17. 18:11ยทPS/C++
๋ชฉ์ฐจ
  1. ๐Ÿค”๋ฌธ์ œ ์ดํ•ด
  2. ๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ
728x90

๋ฐฑ์ค€


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

LCS(longest common sequence)๋ฌธ์ œ๋กœ 11053๋ฒˆ๊ณผ ์œ ์‚ฌํ•˜์ง€๋งŒ n๊ณผ Ai์˜ ํฌ๊ธฐ๊ฐ€ ํ›จ์”ฌ ํฐ ๋ฒ„์ „์˜ ๋ฌธ์ œ์ด๋‹ค.


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

lower_bound๋ฅผ ์ด์šฉํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

์ˆ˜์—ด์ด ์ €์žฅ๋˜์–ด ์žˆ๋Š” arr๊ณผ ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์ฐพ์•„ ๋„ฃ์–ด์ค„ ๋ฒกํ„ฐ v๋ฅผ ์„ ์–ธํ•ด์ฃผ์—ˆ๋‹ค

๊ฐ€์žฅ ๋จผ์ € v์— arr[0] ์›์†Œ๋ฅผ ๋„ฃ์–ด์ฃผ๊ณ  arr์˜ 1๋ฒˆ์งธ ์›์†Œ๋ถ€ํ„ฐ ๋งˆ์ง€๋ง‰๊นŒ์ง€ for๋ฌธ์„ ๋Œ๋ ค์ฃผ์—ˆ๋‹ค.

for๋ฌธ์—์„œ๋Š” v์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ์›์†Œ๋ณด๋‹ค arr[i]๋ฒˆ์งธ ์›์†Œ๊ฐ€ ๋” ํฐ ๊ฒฝ์šฐ์—” v.push_back(arr[i])๋ฅผ ํ•ด์ฃผ์—ˆ๋‹ค.

๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ๋Š” v์—์„œ arr[i]๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์›์†Œ ์ค‘์—์„œ index๊ฐ€ ๊ฐ€์žฅ ์ž‘์€ ์›์†Œ์˜ iterator๋ฅผ ํƒ์ƒ‰ํ•˜๊ณ  ๊ทธ ์œ„์น˜์— arr[i]๋ฅผ ๋„ฃ์–ด์ฃผ์—ˆ๋‹ค. ์ด ๋ถ€๋ถ„์ด ์กฐ๊ธˆ ์ดํ•ด๊ฐ€ ์•ˆ๋˜์—ˆ๋Š”๋ฐ ์•„๋ž˜ ์˜ˆ์‹œ๋ฅผ ๋ณด๋ฉด ๋А๋‚Œ์ด ์˜ฌ ๊ฒƒ์ด๋‹ค.

 

์˜ˆ์ œ๋ฅผ ์‚ดํŽด๋ณด์ž

7
10 20 10 30 20 50 25

์ด ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ ์œ„ ๊ฒฝ์šฐ๋Œ€๋กœ ํ•œ๋‹ค๋ฉด for๋ฌธ์—์„œ i๊ฐ€ 5๊นŒ์ง€ ์ˆ˜ํ–‰ํ•œ ๊ฒฝ์šฐ์— v์˜ ์ƒํƒœ๋Š”

10 20 30 50์ด ๋œ๋‹ค.

i๊ฐ€ 6์ผ ๋•Œ arr[i] = 25์ด๊ณ , v์˜ ๋งˆ์ง€๋ง‰ ์›์†Œ๋Š” 50์ด ๋˜๋Š”๋ฐ ์ด ๊ฒฝ์šฐ์—๋Š” if๋ฌธ์„ ๋งŒ์กฑํ•˜์ง€ ์•Š์•„ else๋ฌธ์œผ๋กœ ๋“ค์–ด๊ฐ„๋‹ค

์—ฌ๊ธฐ์„œ iter์—๋Š” v[2]์ธ 30์— ํ•ด๋‹นํ•˜๋Š” ์œ„์น˜๊ฐ€ ์ €์žฅ๋œ๋‹ค.

๊ทธ ์œ„์น˜์— arr[i]์— ํ•ด๋‹นํ•˜๋Š” 25๊ฐ€ ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค.

๊ทธ๋ ‡๊ฒŒ ๋˜๋ฉด ๋ฒกํ„ฐ v์— ์ €์žฅ๋œ ์›์†Œ๋“ค์€ ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด ์ž์ฒด๋ฅผ ์˜๋ฏธํ•˜์ง€ ์•Š๊ฒŒ ๋˜๋Š”๋ฐ v์˜ size๊ฐ€ ์™œ ๋‹ต์ด ๋˜๋Š”์ง€ ๊ถ๊ธˆํ•  ๊ฒƒ์ด๋‹ค. ์ด๋•Œ v์˜ ์ƒํƒœ๋Š” 

10 20 25 50์ด ๋œ๋‹ค.

์—ฌ๊ธฐ์„œ 25๊ฐ€ 30์˜ ์œ„์น˜์— ๋“ค์–ด๊ฐ„๊ฑด 30์ด ์žˆ์—ˆ๋˜ ์œ„์น˜์—์„œ 25๊ฐ€ 20๋ณด๋‹ค๋Š” ํฌ๊ณ  50๋ณด๋‹ค๋Š” ์ž‘์„ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

30 ๋’ค์— 25๊ฐ€ ์ถ”๊ฐ€๋œ ๊ฒƒ์ด ์•„๋‹ˆ๋ผ 30์ด ์žˆ๋˜ ์ž๋ฆฌ์— ๋“ค์–ด๊ฐ„ ๊ฒƒ์ด๋ฏ€๋กœ 20<x<50์˜ ์ž๋ฆฌ๋ฅผ ๋Œ€์ฒดํ•œ ๊ฒƒ ๋ฟ์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค.


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
int arr[1000001];
vector<int> v;

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];
    }
    v.push_back(arr[0]);
    for (int i = 1; i < n; i++) {
        if (v.back() < arr[i]) v.push_back(arr[i]);
        else {
            auto iter = lower_bound(v.begin(), v.end(), arr[i]);
            *iter = arr[i];
        }
    }
    cout << v.size();
}
728x90

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

[๋ฐฑ์ค€/C++] 6087๋ฒˆ ๋ ˆ์ด์ € ํ†ต์‹   (0) 2022.11.15
[๋ฐฑ์ค€/C++] 15927๋ฒˆ ํšŒ๋ฌธ์€ ํšŒ๋ฌธ์•„๋‹ˆ์•ผ!!  (0) 2022.11.15
[๋ฐฑ์ค€/C++] 11656๋ฒˆ ์ ‘๋ฏธ์‚ฌ ๋ฐฐ์—ด  (0) 2022.11.14
[๋ฐฑ์ค€/C++] 17396๋ฒˆ ๋ฐฑ๋„์–ด  (0) 2022.11.11
[๋ฐฑ์ค€/C++] 20040๋ฒˆ ์‚ฌ์ดํด ๊ฒŒ์ž„  (0) 2022.11.03
  1. ๐Ÿค”๋ฌธ์ œ ์ดํ•ด
  2. ๐Ÿ”ฅํ’€์ด๐Ÿ”ฅ
'PS/C++' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€/C++] 6087๋ฒˆ ๋ ˆ์ด์ € ํ†ต์‹ 
  • [๋ฐฑ์ค€/C++] 15927๋ฒˆ ํšŒ๋ฌธ์€ ํšŒ๋ฌธ์•„๋‹ˆ์•ผ!!
  • [๋ฐฑ์ค€/C++] 11656๋ฒˆ ์ ‘๋ฏธ์‚ฌ ๋ฐฐ์—ด
  • [๋ฐฑ์ค€/C++] 17396๋ฒˆ ๋ฐฑ๋„์–ด
yulee_to
yulee_to
  • yulee_to
    yulee
    yulee_to
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (139) N
      • 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 (32) N
      • Book (39)
        • ์ž๋ฐ”์˜ ์‹  (32)
        • ์Šคํ”„๋ง ์ž…๋ฌธ์„ ์œ„ํ•œ ์ž๋ฐ” ๊ฐ์ฒด ์ง€ํ–ฅ์˜ ์›๋ฆฌ์™€ ์ดํ•ด (7)
      • ETC (4)
        • Blog (3)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

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

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

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

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

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

๊ฐœ์ธ์ •๋ณด

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

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

๋‹จ์ถ•ํ‚ค

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

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

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

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

๋ชจ๋“  ์˜์—ญ

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

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