게시 됨 업데이트 됨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;
}
팔로우

카테고리

최근 글

광고

×