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

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

 

주어진 숫자를 가지고 1을 찾아가는 단순한 방법을 사용하면

테스트케이스의 수가 많아 시간초과에 걸리게 된다.

1로 가게 되는 경우를 거꾸로 생각해서 최적의 계산 횟수를 저장해둔다면 1~1000000 의

모든 경우를 1번만 계산한 후 테스트케이스에 맞게 바로바로 출력해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int arr[1000001];
 
int main() {
    arr[1] = 0, arr[2] = 1, arr[3] = 1, arr[4] = 2;
    int number;
    cin >> number;
 
    for (int i = 5; i <= number; i++) {
        if (i % 2 != 0 && i % 3 != 0) {
            arr[i] = arr[i - 1] + 1;
        }
        else {
            arr[i] = arr[i - 1] + 1;
            if (i % 2 == 0) if (arr[i] > arr[i / 2] + 1) arr[i] = arr[i / 2] + 1;
            if (i % 3 == 0) if (arr[i] > arr[i / 3] + 1) arr[i] = arr[i / 3] + 1;
        }
    }
    printf("%d", arr[number]);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습) 20.02.08

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

14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06

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

 

일반적인 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int lis, n;
int arr[1000];
int Lis[1001];
 
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.10

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

16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06
BOJ 14002번 가장 긴 증가하는 부분수열4  (0) 2019.04.06

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

+ Recent posts

티스토리툴바