BOJ : https://www.acmicpc.net/problem/1937

github : https://github.com/junho0956/Algorithm/blob/master/1937/1937/%EC%86%8C%EC%8A%A4.cpp

 

dfs 와 dp 를 이용하여 문제를 해결하였습니다.

dp[n][m] : (n,m) 에서 이동할 수 있는 최대 횟수를 저장하는 의미

 

lis 알고리즘과 관련된 문제인데 아마도 dfs 와 dp로 돌리는거와 마찬가지로

각 좌표마다 가장 길게 만들 수 있는 부분수열을 찾으라는 의미일 것이다(?) 결국 dfs 돌리시면 됩니다.

 

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
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
typedef pair<int, int> pii;
int n;
int arr[501][501];
bool visit[501][501];
int dp[501][501];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
 
int solve(int y, int x, int pre) {
 
    if (arr[y][x] <= pre) return 0;
 
    int& res = dp[y][x];
    if (res != -1) return res;
 
    visit[y][x] = true;
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < n && xx >= 0 && xx < n && !visit[yy][xx]) {
            ans = max(ans, solve(yy, xx, arr[y][x]) + 1);
        }
    }
 
    visit[y][x] = false;
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
 
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, solve(i, j, 0));
        }
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

복습 20.02.10

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06
BOJ 14002번 가장 긴 증가하는 부분수열4  (0) 2019.04.06
가장 긴 증가하는 부분수열3(12738) - Junnnho  (0) 2019.04.06

BOJ : https://www.acmicpc.net/problem/14003

 

14003번: 가장 긴 증가하는 부분 수열 5

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

4번 문제와 다른점은 배열의 개수와, 표현범위가 10억이라는 점이다.

4번 : https://junho0956.tistory.com/9?category=825556

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
 
int lis, n;
long long arr[1000001];
long long Lis[1000001];
vector<pair<int, long long> > pii;
stack<long long> s;
 
int lower_bound(int start, int end, long long key)
{
    int mid;
    while (end - start > 0)
    {
        mid = (start + end) / 2;
 
        if (Lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i)
        scanf("%lld", &arr[i]);
 
    Lis[0] = arr[0];
    pii.push_back(make_pair(0, Lis[0]));
 
    for (int i = 1; i < n; i++) {
        if (Lis[lis] < arr[i])
        {
            Lis[lis + 1] = arr[i];
            lis++;
 
            pii.push_back(make_pair(lis, arr[i]));
        }
        else
        {
            int ans = lower_bound(0, lis, arr[i]);
            Lis[ans - 1] = arr[i];
 
            pii.push_back(make_pair(ans - 1, arr[i]));
        }
    }
 
    printf("%d\n", lis + 1);
 
    for (int i = pii.size(); i >= 0; i--) {
        if (pii[i - 1].first == lis) {
            s.push(pii[i - 1].second);
            lis--;
        }
        if (lis == -1) break;
    }
 
    while (!s.empty()) {
        printf("%lld ", s.top()), s.pop();
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14002번 가장 긴 증가하는 부분수열4  (0) 2019.04.06
가장 긴 증가하는 부분수열3(12738) - Junnnho  (0) 2019.04.06
가장 긴 증가하는 부분수열2(12015) - Junnnho  (0) 2019.04.06

BOJ : https://www.acmicpc.net/problem/14002

 

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

www.acmicpc.net

lis 알고리즘의 가장 큰 문제점은 길이는 정확하게 알수 있는데,

그 값을 찾아가는 과정을 정확하게 알아내지 못한다는 점이다.

같은 수가 나오거나, 길이는 같은데 다른 값이 갱신된다던가 하는 문제이다.

이 때는, lis배열 뿐만아니라 스택과 값을 저장할 벡터를 추가하여 문제를 해결한다.

벡터는 pair로 입력받아, lis에 추가되는 인덱스와 값을 동시에 넣어준다.

lis의 길이를 찾는 과정이 끝나면,

벡터의 끝부분부터 pair의 lis가 같을때 스택에 추가해주고 erase;

그 다음, 스택에 있는 값을 순서대로 출력해주면 된다.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
 
int lis, n;
int arr[1001];
int Lis[1001];
vector<pair<int, int> > pii;
stack<int> s;
 
int lower_bound(int start, int end, int target)
{
    int mid;
    while (end - start > 0)
    {
        mid = (start + end) / 2;
 
        if (Lis[mid] < target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    Lis[0] = arr[0];
    pii.push_back(make_pair(0, Lis[0]));
 
    for (int i = 1; i < n; i++) {
        if (Lis[lis] < arr[i])
        {
            Lis[lis + 1] = arr[i];
            lis++;
 
            pii.push_back(make_pair(lis, arr[i]));
        }
        else
        {
            int ans = lower_bound(0, lis, arr[i]);
            Lis[ans - 1] = arr[i];
 
            pii.push_back(make_pair(ans - 1, arr[i]));
        }
    }
 
    printf("%d\n", lis + 1);
 
    for (int i = pii.size(); i >= 0; i--) {
        if (pii[i - 1].first == lis) {
            s.push(pii[i - 1].second);
            lis--;
        }
        if (lis == -1) break;
    }
 
    while (!s.empty()) {
        printf("%d ", s.top()), s.pop();
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

복습 20.02.09

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06
가장 긴 증가하는 부분수열3(12738) - Junnnho  (0) 2019.04.06
가장 긴 증가하는 부분수열2(12015) - Junnnho  (0) 2019.04.06

BOJ : https://www.acmicpc.net/problem/12738

 

12738번: 가장 긴 증가하는 부분 수열 3

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

전 문제와는 다르게 음수값이 추가된것 밖에 없다.

소스는 역시 똑같다.

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int lis, n;
int arr[1000000];
int Lis[1000001];
 
int lower_bound(int start, int end, int key) {
    int mid;
    while (start < end) {
        mid = (start + end) / 2;
        if (Lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    lis = 0, Lis[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > Lis[lis]) {
            Lis[lis + 1] = arr[i], lis++;
        }
        else {
            int ans = lower_bound(0,lis,arr[i]);
            Lis[ans-1] = arr[i];
        }
    }
    cout << lis+1;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습 20.02.09

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06
BOJ 14002번 가장 긴 증가하는 부분수열4  (0) 2019.04.06
가장 긴 증가하는 부분수열2(12015) - Junnnho  (0) 2019.04.06

+ Recent posts

티스토리툴바