https://www.acmicpc.net/problem/2565


나무위키 최장증가부분수열


사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞여 있고, 'A씨, 맨 뒤 / 맨 앞으로 가세요', 'A씨, B씨와 C씨 사이로 가세요' 꼴의 명령으로 사람들을 이동시킨다고 하자.)


이 문제는 전형적인 LIS 응용 문제이다. 움직인 사람들의 총 수가 최소가 된다는 말은 움직이지 않은 사람들의 수가 최대가 된다는 것이다.

사람들의 번호들의 수열에서 이미 오름차순으로 정리된 쌍이 있다면 그들은 움직이지 않아도 된다. 따라서 그 수열의 LIS를 이루는 사람들은 움직이지 않고, 나머지 사람들이 그들 사이로 적절히 배열된다면 정렬할 수 있다. 


정렬 -> LIS -> 전깃줄 개수 - 수열 크기


난최고야!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
 
struct wire
{
    int A;
    int B;
};
 
wire arr[101];
int dp[101];
 
bool cmp(wire& first, wire& second)
{
    if (first.A < second.A)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> arr[i].A >> arr[i].B;
    }
    std::sort(arr, arr + N, cmp);
    
    int back = 0;
    for (int i = 0; i < N; ++i)
    {
        int it = 0;
        for( ;dp[it] != 0; ++it)
        {
            if (dp[it] > arr[i].B)
            {
                dp[it] = arr[i].B;
                break;
            }
        }
        dp[it] = arr[i].B;
        back = back > it ? back : it;
    }
    std::cout << N - (back + 1);
    return 0;
}
cs


끼에에에에에에에에엒!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1912: 연속합(DP)  (0) 2019.08.27
백준 9251: LCS(DP)  (0) 2019.08.26
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19

nlogn으로 풀어본다고 개삽질하다가 지쳐서


n2으로 무식하게 오름차순 내림차순 다 계산해서 배열에 때려박은다음


계산된 배열 두개중 합친 값이 가장 큰걸 반환하게 했다.


솔찍히 시간초과 날줄알앗는데 으..응?으응???하니까 정답입니다!!...


아몰라 ㄹ풀었음댓지머


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
 
int seq[1010];
int highDp[1010];
int lowerDp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = highDp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && highDp[j] > m)
                m = highDp[j];
        highDp[i] = m + 1;
        
    }
 
    for (int i = N; i >= 1; --i)
    {
        int m = 0;
        for (int j = N + 1; j >= i; --j)
            if (seq[i] > seq[j] && lowerDp[j] > m)
                m = lowerDp[j];
        lowerDp[i] = m + 1;
    }
 
    int mx = 0;
    for (int i = 0; i <= N; ++i)
    {
        mx = lowerDp[i] + highDp[i] < mx ? mx : lowerDp[i] + highDp[i];
    }
    std::cout << mx - 1;
    return 0;
}
 
cs


으으 왤캐 깔끔하게 안풀리지?

저작자표시

'알고리즘' 카테고리의 다른 글

백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16

https://www.acmicpc.net/problem/11053


어제의 알고리즘 대실패는 나로 하여금 나 자신이 빡통이라는걸 절절히 인정하는 그러한 계기가 되었다.


그래서 오늘 문제는 바로 갓무위키를 찾아보았다.


부분수열이 뭔지 까먹었기도 하고ㅎ


꺼라위키 정의


어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.

이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.


예를 들어 다음 수열이 주어졌다고 하자.


3 5 7 9 2 1 4 8


위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.


3 7 9 1 4 8 (5, 2 제거)

7 9 1 8 (3, 5, 2, 4 제거)

3 5 7 8 (9, 2, 1, 4 제거)

1 4 8 (3, 5, 7, 9, 2 제거)


이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다.


그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.

부분수열 3 5 7 8은 LIS이다.


한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열


5 1 6 2 7 3 8


에서 부분수열


1 2 3 8

5 6 7 8


은 모두 길이가 4인 LIS이다. 


부분수열은 간단히 말해서 임의의 수열 A에서 A의 원소를 포함하는 또다른 수열 B라고 보면 된다.


여기서 수열이라고 해서 좀 혼란스러웠는데, 수열은 보통 일정한 규칙이 존재하는 수의 집합이라고 봐야 하지만 여기선 없다고 봐도 상관 없다.


즉 걍 숫자 집합인데, 부분수열은 그냥 부분집합이다. 대신 숫자의 순서가 보장되어있는 집합이지


꺼라위키도 설명을 그지같이 했다. 몇 개의 숫자를 제거한다니, 제거하는 규칙이 있어야하는것마냥 설명해놓곤


걍 수열 A의 숫자 몇개 추려서 다른 수열 B 만들면 그게 A의 부분수열이다.(순서는 반드시 보장되어야 한다. 자세한 예시는 꺼라위키 정의 참고)


암튼, 그런 부분수열중에 오름차순으로 되어 있는 수열 x중 사이즈가 가장 큰 수열의 사이즈를 반환하는 문제다.


꺼라에서는 n제곱으로 푸는 방법과, n로그n으로 푸는 방법 둘 다 설명해놨는데 n제곱으로 풀어봤더니 통과된다.


알고리즘 푸는 방법은 혼자서 생각 못할 것 같아 어쩔 수 없이 봤지만...그래도 코드 구현은 직접 했다...


나도 똑똑해졌으면 좋겠구만


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
 
int seq[1010];
int dp[1010];
 
bool cmp(int first, int second)
{
    if (first > second)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = dp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && dp[j] > m)
                m = dp[j];
        dp[i] = m + 1;
    }
    std::sort(dp, dp + N + 1, cmp);
    std::cout << dp[0];
    return 0;
}
cs


여기서 sort를 사용했는데, 사실 max 변수 하나 만들어서 dp중 가장 큰 수를 max에 담아 출력하기만 하면 더 빠를 것이다


나는 그냥 좀 더 깔끔해보이려고 이렇게 뺐다. 문제는 없이 통과되던데


nlogn으로 푸는 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
 
int seq[1010];
int dp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    int back = 0;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int it = 1;
        while (dp[it] != 0)
        {
            if (dp[it] >= seq[i])
            {
                dp[it] = seq[i];
                break;
            }
            ++it;
        }
        if (dp[it] == 0)
        {
            dp[it] = seq[i];
            back = it;
        }
    }
    std::cout << back;
    return 0;
}
cs


설명은 귀찮아서 생략


일케 하면 빠른대신에 모든 데이터들의 증가부분수열을 저장할수는 없다.

저작자표시

'알고리즘' 카테고리의 다른 글

백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 2579: 계단 오르기(DP)  (0) 2019.08.14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
unsigned int dp[101][10];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 1; i <= 9; ++i)
        dp[1][i] = 1;
    for (int i = 2; i <= N; ++i)
        for (int j = 0; j < 10; ++j)
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
        }
    unsigned long long ans = 0;
    for (int i = 0; i < 10; ++i)
        ans += dp[N][i];
    std::cout << ans % 1000000000;
    return 0;
}
cs


십억을 중간과정에서 나머지연산하면 오버플로는 막겠지만 값이 변하지 않나..


하... 모르겠다...


그냥 전체적으로 조졌다... 왜 일케 하는지는 알겠는데 내가 직접 로직을 세우지도 못했고... 아직도 나머지연산은 이해가 안대고... DP빡고수라고 자화자찬 하자마자 개뚜드려맞았다...

저작자표시

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 2579: 계단 오르기(DP)  (0) 2019.08.14
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

+ Recent posts

티스토리툴바