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

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

 

문제 해결을 위한 알고리즘 : lis, dp, greedy

lis 알고리즘을 이용하여 문제를 해결하였고

꼬이지않은 lis 배열 안에 들어간 size 가 최대한 연결할 수 있는 포트가 된다.

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef vector<int> LIS;
LIS lis;
int main() {
    int n, arr[40001], L;
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    L = 0, lis.push_back(arr[0]);
 
    for (int i = 1; i < n; i++) {
        if (arr[i] > lis[L])
            lis.push_back(arr[i]), L++;
        else {
            vector<int>::iterator ans = lower_bound(lis.begin(), lis.end(), arr[i]);
            *ans = arr[i];
        }
    }
 
    printf("%d", lis.size());
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습 20.02.10

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

백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14
2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08
BOJ 2565번 전깃줄  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07
6603번 : 로또 - junnnho  (0) 2019.04.07

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

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

 

오름차순 정렬이 되어있어야하고, lis 알고리즘에서 lower_bound의 의미를 알아보자면

ex) 만약 현재 lis의 마지막 second가 5이고 현재 걸려있는 줄의 second가 4이면 꼬여있는 상태가 됨을 의미하고,

     만약 현재 lis의 마지막 second가 5이고 현재 걸려있는 줄의 second가 6이면 꼬이지 않은 상태가 됨을 의미한다.

 

꼬일때 lower_bound -> 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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int, int> > v;
int lis[501];
int n, f, s, cnt, L;
 
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() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &f, &s);
        v.push_back(make_pair(f, s));
    }
    sort(v.begin(), v.end());
    lis[0] = v[0].second;
    for (int i = 1; i < n; i++) {
        if (lis[L] < v[i].second) {
            lis[++L] = v[i].second;
        }
        else {
            int ans = _lower_bound(0, L, v[i].second);
            lis[ans - 1] = v[i].second;
            cnt++;
        }
    }
    printf("%d", cnt);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습 20.02.10

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

2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08
BOJ 2352번 반도체 설계  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07
6603번 : 로또 - junnnho  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07

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

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

 

임의의 오늘(today)부터 일을 시작하여 걸리는 시간(arr[today][0])이 만약 총날짜(N) 보다 같거나 작다면

나는 오늘(today)부터 일해도 되는 것이고, 일이 끝난 today+arr[today][0] 의 날짜부터 일을 재개하면 된다.

결국 첫시작일인 1일부터 N일이 주어지면 1부터 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
#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
int N;
int arr[16][2];
 
int ans(int today) {
    if (today > N) return 0;
 
    int temp = 0;
    if (today + arr[today][0] - 1 <= N)
        temp = ans(today + arr[today][0]) + arr[today][1];
 
    temp = max(temp, ans(today + 1));
    return temp;
}
 
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &arr[i][0],&arr[i][1]);
    }
 
    printf("%d", ans(1));
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

복습) 20.02.08

 

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

BOJ 2352번 반도체 설계  (0) 2019.04.08
BOJ 2565번 전깃줄  (0) 2019.04.08
6603번 : 로또 - junnnho  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07

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

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : BFS, Brute force, DFS, back tracking

 

백트래킹의 간단한 입문 문제이다.

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
#include <cstdio>
#include <vector>
using namespace std;
 
int N;
int arr[13];
vector<int> v;
 
void dfs(int start) {
    if (v.size() == 6) {
        for (int i = 0; i < 6; i++) {
            printf("%d ", v[i]);
        }
        printf("\n");
        return;
    }
 
    for (int i = start; i < N; i++) {
        if (v.size() < 6) {
            v.push_back(arr[i]);
            dfs(i + 1);
            v.pop_back();
        }
    }
}
 
int main() {
    while (1) {
        scanf("%d", &N);
        if (N == 0) break;
        for (int i = 0; i < N; i++) {
            scanf("%d", &arr[i]);
        }
        dfs(0);
        printf("\n");
    }
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

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

BOJ 2565번 전깃줄  (0) 2019.04.08
BOJ 14501번 퇴사  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07

+ Recent posts

티스토리툴바