게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 201 단어)

<11054> 가장 긴 바이토닉 부분 수열

문제 : https://www.acmicpc.net/problem/11054

먼저 증가하는 수열의 최대 길이와 감소하는 수열의 최대 길이를 구해주었습니다.
그 후 각 자리의 최대 길이를 서로 더해준 후 max 값을 비교하여 해결했습니다.

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int max_value = 0;
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> plus(n); // 증가하는 수열의 최대 길이
    vector<int> minus(n); // 감소하는 수열의 최대 길이

    for (int i = 0; i < n; i++) {
        plus[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && plus[i] < plus[j] + 1) {
                plus[i] = plus[j] + 1;
            }
        }
    }

    for (int i = n-1; i >= 0; i--) {
        minus[i] = 1;
        for (int j = n-1; j > i; j--) {
            if (a[j] < a[i] && minus[i] < minus[j] + 1) {
                minus[i] = minus[j] + 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        max_value = max(max_value, plus[i] + minus[i] - 1);
    }

    cout << max_value << '\n';

    return 0;
}
 게시 됨 업데이트 됨Algorithm / BOJ2분안에 읽기 (약 356 단어)

<2632> 피자판매

문제 : https://www.acmicpc.net/problem/2632

피자가 붙어있어야 한다는 조건 때문에 정렬을 할수가 없었습니다. 먼저 A와 B 각각의 피자판에서 만들어 질 수 있는 모든 합의 경우를 map을 사용해 저장한 후 목표하는 크기의 피자를 만들 수 있는 경우를 출력하는식으로 문제를 해결했습니다.

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
#include <iostream>
#include <vector>
#include <map>

#define MAX_SIZE 1000
using namespace std;

int target;
int m, n;
int a[MAX_SIZE], b[MAX_SIZE];
map<int, int> a_sum, b_sum;

void get_all_sum(int* arr, map<int, int>& sum_map, int size) {
    for (int i = 1; i < size; i++) { // 1개~suze-1개로 만들 수 있는 경우 모두 구하기
        for (int j = 0; j < size; j++) { // 시작하는 피자 순서
            int sum = 0;
            for (int k = 1; k <= i; k++) { // j번째 피자부터 i개 만큼 더하기
                if (j+k-1 < size) {
                    sum += arr[j+k-1];
                } else {
                    sum += arr[j+k-1-size];
                }
            }
            sum_map[sum] = sum_map[sum] + 1;
        }
    }

    int sum = 0;
    for (int i = 0; i < size; i++) { // 피자의 모든 조각(size) 합
        sum += arr[i];
    }
    sum_map[sum] = 1;

    return ;
}

int main() {
    ios_base::sync_with_stdio (false);

    cin >> target >> m >> n;

    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        cin >> b[j];
    }

    get_all_sum(a, a_sum, m);
    get_all_sum(b, b_sum, n);

    int cnt = a_sum[target] + b_sum[target]; // a와 b 각각의 피자만 사용해서 만드는 경우
    for (int i = 1; i < target; i++) { // a와 b피자 같이 사용해서 만드는 경우
        if (a_sum[i] && b_sum[target-i]) {
            cnt += (a_sum[i] * b_sum[target-i]);
        }
    }

    cout << cnt << '\n';

    return 0;
}

 게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 204 단어)

<5014> 스타트링크

문제 : https://www.acmicpc.net/problem/5014

BFS를 사용해 쉽게 해결할 수 있습니다. 다만 if 문에서 visit 배열로 층의 방문 여부를 체크하기전에 배열의 index가 유효한 범위에 속해있는지 확인을 먼저해주어야 합니다.

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
#include <iostream>
#include <queue>
#include <vector>

#define MAX_SIZE 1000001
using namespace std;

bool visit[MAX_SIZE];
int cnt[MAX_SIZE];

int main() {
    int f, s, g, u, d; // 전체 층, 현재 층, 목표 층, 업 층, 다운 층
    cin >> f >> s >> g >> u >> d;

    queue<int> q; // 층수
    visit[s] = true;
    cnt[s] = 0;
    q.push(s);

    while(!q.empty()) {
        int now_floor = q.front();
        int now_cnt = cnt[now_floor];
        q.pop();

        int next1 = now_floor + u;
        int next2 = now_floor - d;

        if (next1 < MAX_SIZE && visit[next1] == false) {
            q.push(next1);
            visit[next1] = true;
            cnt[next1] = now_cnt + 1;
        }

        if (next2 > 0 && visit[next2] == false)  {
            q.push(next2);
            visit[next2] = true;
            cnt[next2] = now_cnt + 1;
        }
    }

    if (visit[g] == true) {
        cout << cnt[g] << '\n';
    } else {
        cout << "use the stairs" << '\n';
    }

    return 0;
}

 게시 됨 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 165 단어)

<14501> 퇴사

문제 : https://www.acmicpc.net/problem/14501

N의 범위가 최대 15로, 작은 경우에 속해서 완전 탐색을 했습니다. 상담을 하는 경우와 하지 않는 경우를 나누어 해결합니다.
상담이 필요한 기간에 당일 부터 포함되는 것만 주의하여 범위를 계산하면 될 것 같습니다

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
#include <iostream>
#include <algorithm>

#define MAX_SIZE 16

using namespace std;

int day[MAX_SIZE];
int pay[MAX_SIZE];
int n;

int sum = 0;

void go(int d, int s) {
    if (d == n + 1) {
        sum = max(sum, s);
        return;
    }

    if (d + day[d] <= n + 1) {
        go(d + day[d], s + pay[d]);
    }
    if (d + 1 <= n + 1) {
        go(d + 1, s);
    }
}

int main(void) {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> day[i] >> pay[i];
    }

    go(1, 0);

    cout << sum << '\n';

    return 0;
}
팔로우

카테고리

최근 글

광고

×