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

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

dfs를 통해 모든 수를 다 방문하면서 합이 같아지는 부분이 있는지 확인했다.

 

1개는 현재의 합에서 현재 방문한 수를 빼고 다음수를 확인하는 재귀,

1개는 현재의 합을 그대로 다음수를 확인하는 재귀

총 2개의 재귀를 이용하면 쉽게 해결된다.

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

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

BOJ 14501번 퇴사  (0) 2019.04.07
6603번 : 로또 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07

+ Recent posts

티스토리툴바