문제

 

풀이

처음 이 문제를 봤을 때 지문에 대한 이해를 전혀 못했습니다.

말을 1인 1개씩 2개를 놓고 게임을 하는건지, 말 1개를 놓고 둘이서 게임을 하는건지도 이해가 안돼서 로직을 그리는 내내 예시도 맞지 않아서 답답했었습니다.

 

문제를 이해하는데 4시간은 걸린것 같습니다.

이 문제는 말을 1개만 놓고 둘이서 게임하는게 맞고, 1번 정점이 루트인 트리라고 명시가 되어있기 때문에 1번 정점부터 방향그래프처럼 순회하도록 합니다.

 

한 번씩 번갈아가면서 점수를 가져가기 때문에 선공의 입장에서는 +, 후공의 입장에서는 -으로 계산할 수 있습니다.

서로 최대한 이기려고 할 것이고, 이기는 경우가 하나라도 존재한다면 이기는 것이기 때문에 가능한 높은 점수를 얻는 것이 중요합니다.

그럴려면 자식 노드의 점수들 중 최솟값을 본인 점수에서 빼는 것으로 계산할 수 있습니다.

선공의 입장에서 계산했기 때문에 해당 노드의 점수가 0 이상이면 선공의 승리, 음수면 후공의 승리가 될 것입니다.

 

2번째 예시로 로직을 설명드리면 루트는 1번, 리프는 4, 5, 6번 노드입니다.

4, 5, 6번 노드에 도착하면 해당 번호만큼 점수를 추가합니다. 그러면 4, 5, 6번 노드의 점수는 4, 5, 6입니다.

 

2번 노드에서는 자신의 번호인 2에서 유일한 자식인 4번 노드의 점수 4를 뺀 값을 저장합니다. 그러면 2번 노드의 점수는 -2가 됩니다.

 

3번 노드는 자식이 2개 있습니다.

5번, 6번 노드의 점수 중 최솟값을 3에서 빼줍니다. 그러면 3번 노드의 점수는 3 - 5 = -2 입니다.

 

마지막 1번 노드입니다.

1번 노드의 자식인 2, 3번 노드 모두 점수가 -2이므로 1 + 2 = 3 점을 얻습니다.

 

그러면 최종 점수 배열은 [3, -2, -2, 4, 5, 6] 이 되고, 0 이상의 점수에는 1, 음수 점수에는 0을 출력하도록 합니다.

 

 

코드

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
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
bool visit[MAX];
int score[MAX];
int N;
 
int dfs(int v) {
    visit[v] = true;
 
    int tmp = 1e9;
    for (auto next : graph[v]) {
        if (visit[next]) continue;
        tmp = min(tmp, dfs(next));
    }
    if (tmp == 1e9) tmp = 0;
 
    return score[v] = -tmp + v;
}
 
void func() {
    dfs(1);
 
    for (int i = 1; i <= N; i++) {
        if (score[i] >= 0) cout << "1\n";
        else cout << "0\n";
    }
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22
엘리스 코드 챌린지 Day 1 목표량  (0) 2024.07.22

문제

 

풀이

괄호 안에 존재하는 수를 괄호 바로 앞에 있는 수만큼 반복한 문자열로 만들 수 있고, 모든 괄호를 제거했을 때 문자열의 길이를 구하는 문제입니다.

처음에는 재귀를 통해서 문자열을 직접 구해서 해결했었는데

어떤분께서 게시글에 int 범위가 벗어난다는 의견을 제시해주셔서 다시 풀게 되었습니다. 아마 저는 틀렸겠지요... ㅠ

 

생각해보니 문자열을 직접 구할 필요가 없더라고요! 길이만 구하면 되니까요!

그래서 이번에는 스택으로 접근했습니다.

문제의 핵심은 괄호 안의 숫자를 k번 반복한다는 것입니다.

그러면 괄호 안의 숫자의 길이 * k가 스택에 들어가면 된다는거겠죠.

 

그러면 스택에는 숫자와 괄호를 구분할 필요가 생깁니다.

우선 숫자가 나온다면 다음 문자가 "(" 인지 확인해야 합니다.

다음 문자가 "("가 아니라면 스택에 1을 넣으시면 됩니다. (길이가 1인 문자열)

다음 문자가 "("이라면 반복에 활용되는 k에 해당되기 때문에 해당 숫자를 스택에 넣습니다.

 

다음은 괄호가 나왔을 경우입니다.

현재 위치가 "("이면 괄호 구분을 위해 스택에 -1을 넣습니다.

스택에는 양의 정수만 들어가기 때문에 이런 방식으로 숫자와 괄호를 구분할 수 있습니다.

 

현재 위치가 ")"이면 스택에 쌓여있는 문자열의 길이들을 더해주도록 합니다.

괄호 짝인 -1이 나올 때까지만 더해주시면 됩니다.

그리고 -1 바로 다음에 있는 수를 꺼내서 곱한 값을 스택에 다시 넣어줍니다.

그러면 3(8) = 888의 과정이 마무리된 것입니다.

-1이 열리는 괄호가 되겠고, 바로 다음에 있는 수가 3에 해당됩니다. 8은 당연히 -1이 나오기 전까지 더한 값들이 됩니다.

 

위 과정들이 모두 끝난다면 스택에는 문자열의 길이가 여러개 들어있을 것입니다.

그 숫자들을 모두 더해주시면 답을 구할 수 있습니다.

문제에는 수의 범위가 명시되어있지 않기 때문에 lnog long 자료형으로 출력해주도록 합니다.

 

코드

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
#include <iostream>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
 
string str;
int N;
 
void func() {
    stack<ll> s;
    for (int i = 0; i < N; i++) {
        if (str[i] == '(') {
            s.push(-1);
        }
        else if (str[i] == ')') {
            ll sum = 0;
            while (1) {
                ll x = s.top();
                s.pop();
                if (x == -1) break;
                sum += x;
            }
            ll tmp = s.top();
            s.pop();
            s.push(tmp * sum);
        }
        else if (i < N - 1 && str[i + 1] == '(') {
            s.push((ll)(str[i] - '0'));
        }
        else s.push(1LL);
    }
 
    ll ret = 0;
    while (!s.empty()) {
        ret += s.top();
        s.pop();
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22
엘리스 코드 챌린지 Day 1 목표량  (0) 2024.07.22

문제

 

풀이

주어진 배열에서 l ~ r의 범위를 골라서 오름차순으로 정렬하고 idx번째에 위치한 수를 구하는 문제입니다.

N = 10000, M = 500이므로 브루트포스를 사용하여 M * N * logN 시간으로 해결할 수 있습니다.

저는 l ~ r 범위의 수들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬하여 idx번째 수를 출력하는 방식으로 해결했습니다.

 

코드

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 <vector>
#include <algorithm>
#define MAX 10001
using namespace std;
 
int list[MAX];
int N, M;
 
void func() {
    int l, r, idx;
    while (M--) {
        cin >> l >> r >> idx;
        vector<int> tmp;
        for (int i = l; i <= r; i++) {
            tmp.push_back(list[i]);
        }
        sort(tmp.begin(), tmp.end());
        cout << tmp[idx - 1] << '\n';
        tmp.clear();
    }
}
 
void input() {
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 1 목표량  (0) 2024.07.22

문제

 

풀이

입력에서 주어지는 N과 숫자의 구성이 같으면서 더 큰수 라고 한다면 순열 조합 문제라는 것을 떠올리실 수 있습니다.

숫자 구성을 모두 사용해야 하므로 이 문제는 순열입니다.

 

정답이 반드시 있는 경우만 입력으로 주어지므로 54321 처럼 다음 순열이 없는 경우는 없습니다.

따라서 예외 처리 없이 다음 순열을 구해주시기만 하면 됩니다.

C++에는 algorithm 라이브러리에서 next_permutation 메소드를 지원해주기 때문에 편하게 해결할 수 있었습니다.

 

코드

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string N;
 
void func() {
    next_permutation(N.begin(), N.end());
    cout << N << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22

https://www.acmicpc.net/problem/27468

 

1 ~ N이 한번씩 등장하고, i, i + 1번째 수의 차이보다 i + 1, i + 2번째 수의 차이가 2배거나 0.5배인 수열을 만드는 문제입니다.

이 문제는 애드혹 문제로 직접 정답의 패턴을 찾을 수 있다면 구현 자체는 간단하게 할 수 있습니다.

 

저는 1부터 시작하여 정답을 찾던 도중

1 3 2 4 / 5 7 6 8 / 9 11 10 12 ... 이라는 패턴을 찾을 수 있었고, 4개 단위로 끊어서 정답을 구할 수 있다고 생각했습니다.

하지만 위의 정답은 반례가 하나 존재하며, N = 6, 10일 때를 보시면 7과 11이 6과 10보다 먼저 등장함을 알 수 있습니다.

따라서 N % 4 == 2인 경우와 N % 4 != 2인 경우를 분리하여 정답을 구했습니다.

 

N % 4 == 2일 때는 1 2 4 3 / 5 6 8 7 / 9 10 12 11 이라는 패턴을 찾을 수 있고, 이전 4개에서 +4를 한 값이 된다는 것을 알 수 있습니다.

그러면 찾은 패턴 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
 
int list[4];
int N;
 
void init(int t) {
    if (t) {
        list[0] = 1;
        list[1] = 2;
        list[2] = 4;
        list[3] = 3;
    }
    else {
        list[0] = 1;
        list[1] = 3;
        list[2] = 2;
        list[3] = 4;
    }
    
}
 
void func() {
    init(N % 4 == 2);
 
    cout << "YES\n";
    int idx = 0;
    while (N--) {
        cout << list[idx] << ' ';
        list[idx] += 4;
        idx = (idx + 1) % 4;
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > ad-hoc' 카테고리의 다른 글

boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25
boj 14675 단절점과 단절선  (0) 2024.07.23
boj 1377 버블 소트  (0) 2024.06.07

https://www.acmicpc.net/problem/8330

 

수열이 a1, a2, ..., an 으로 주어졌을때 1 ~ ai 범위의 숫자를 적절하게 골라서 1 ~ N의 수가 하나씩 등장하도록 만들어야 합니다.

 

5
3 4 3 2 5

즉 이런 수열이 주어졌을 때

a1은 1 ~ 3 중에서 2

a2는 1 ~ 4 중에서 4

a3은 1 ~ 3 중에서 3

a4는 1 ~ 2 중에서 1

a5는 1 ~ 5 중에서 5

이렇게 골라서 1 ~ N까지 하나씩 등장하도록 순열을 만들 수 있습니다.

그리고 수열을 M번 수정하여 각각 수정된 수열에서도 위처럼 1 ~ N을 만들 수 있는지 구하는 문제입니다.

 

이 문제에서 저는 Segment Tree Lazy를 사용했고, 트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.

1 ~ 5가 있다면

1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있습니다.

5 5 5 5 5가 입력된다면 5에서 수를 5번 고른다는 뜻입니다.

만약 4 4 4 4 4가 입력된다면 5개의 4에서 1 ~ 5를 하나씩 만들 수가 없게 되는거죠.

그렇게 i ~ N을 +1씩 업데이트를 해주고, 각각 노드에서의 최솟값으로 갱신하도록 합니다.

 

그 다음에는 최초로 주어진 수열에서 1 ~ N을 만들 수 있는지 먼저 확인합니다.

list[i]를 사용한게 되기 때문에 list[i] ~ N의 범위에 -1로 업데이트를 시켜줍니다.

트리를 최솟값으로 저장한 이유는 이 연산 과정에서 해당 값의 카운트가 음수인 경우를 빠르게 캐치하기 위해서입니다.

수열의 모든 수를 대상으로 업데이트가 끝난다면 query 함수를 이용하여 트리의 최솟값을 가져옵니다.

최솟값이 0 이상이면 순열을 만들 수 있고, 음수면 만들 수 없습니다.

 

다음 할 작업은 idx번째 수를 x로 변경하는 것입니다.

처음에는 위에서 -1로 업데이트를 한걸 되돌려야 하는지 고민했었는데 결과적으로 시간초과가 뜨더라고요!

N은 20만, M은 50만이기 때문에 시간초과가 당연한거였습니다.

20만개의 수를 50만번 업데이트 해야되니까요.. ㅎ

 

좀더 고민했을때는 트리에는 수열에 대한 카운팅이 각각 진행된 상태였고,

어차피 업데이트되는 idx번째 수에 대해서만 카운팅을 바꿔주면 된다는 결론이 나왔습니다.

그래서 수를 업데이트 하기 전에 기존 list[idx]의 범위에 대한 업데이트를 +1로 진행해주고,

새로운 값인 x의 범위에 대한 업데이트를 -1으로 진행해주면 새로운 수열에서의 카운팅 작업이 완료되는 것입니다.

마지막에는 업데이트된 트리의 최솟값을 가져와서 0 이상이면 `TAK`을, 음수면 `NIE`를 출력해주시면 되겠습니다.

 

 

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
 
int list[MAX];
int tree[MAX << 2];
int lazy[MAX << 2];
int N, M;
 
void lazyUpdate(int node, int l, int r) {
    if (!lazy[node]) return;
    tree[node] += lazy[node];
    if (l != r) {
        lazy[node << 1] += lazy[node];
        lazy[(node << 1) + 1] += lazy[node];
    }
    lazy[node] = 0;
}
 
int update(int node, int l, int r, int s, int e, int diff) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return tree[node];
    if (s <= l && r <= e) {
        lazy[node] += diff;
        lazyUpdate(node, l, r);
        return tree[node];
    }
 
    int m = (l + r) >> 1;
    return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
 
int query(int node, int l, int r, int s, int e) {
    lazyUpdate(node, l, r);
    if (l > e || s > r) return 0;
    if (s <= l && r <= e) return tree[node];
 
    int m = (l + r) >> 1;
    return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        update(1, 1, N, i, N, 1);
    }
 
    for (int i = 0; i < N; i++) {
        update(1, 1, N, list[i], N, -1);
    }
}
 
void print() {
    if (query(1, 1, N, 1, N) >= 0) cout << "TAK\n";
    else cout << "NIE\n";
}
 
void func() {
    init();
    print();
 
    int idx, x;
    while (M--) {
        cin >> idx >> x;
        update(1, 1, N, list[idx - 1], N, 1);
        update(1, 1, N, x, N, -1);
        list[idx - 1] = x;
        print();
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    cin >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 4442 빌보의 생일  (0) 2024.08.01
boj 1517 버블 소트  (0) 2024.06.16
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

https://code-challenge.elice.io/courses/95930/info

 

알고리즘 코드 챌린지 예선 도전하기 | 엘리스 코드 챌린지

 

code-challenge.elice.io

엘리스에서 알고리즘 챌린지를 개최했다. 나는 지인의 추천을 받아서 알게되었고, 1의 망설임도 없이 참여했다.

 

우선 진행 방식은 예선 / 본선으로 나뉘고,

예선은 평일에 온라인으로 2주간 진행되며, 매일 1문제씩 나오는 것을 풀기만 하면 된다.

그리고 함께 공개되는 강의를 수강할 수 있다.

예선 성적 상위 50명이 오프라인 본선으로 진출하게 된다.

 

예선 1주차

1주차라서 그런지 백준 난이도 실버3 ~ 골드4 정도의 쉬운 문제들이 출제되었다.

문제 뜻을 이해하지 못해서 꽤 시간이 걸린 문제도 있었지만 당일에 모두 AC를 받았다.

로직 자체도 어렵지 않고 무난하게 했던것 같다.

이렇게되면 본선 진출자 선발을 어떻게 하려나 라는 생각을 했다.

 

예선 2주차

1주차가 왜 쉬웠는지 6일차부터 말해주는것 같았다.

2가지 방법으로 풀었고, 이건 반례가 있을 수 없다고 확신했기 때문에 더 충격이었던것 같다.

근데 아무리 수정하고 제출해도 60점만 나왔고, 내 접근 방법은 틀렸다가 결론이 되었다.

거의 하루종일 다른 방법 찾기에 매달려있었고, 시간을 넘겨서 60점으로 마무리했다.

이날 정답자 100명을 종료 30분 전에 채운만큼 난이도가 있었던 것으로 보인다. (다른 날은 저녁 전에는 100명을 채웠던 걸로 기억)

 

그리고 7일차는 필기만 끄적이다가 솔루션을 찾지 못했다.

보통 애드혹 문제는 풀이를 보면 "와 이생각을 못했네" 라는 생각이 바로 드는데 이 문제가 그랬다.

 

8일차는 dp가 나왔다.

내가 dp를 제일 좋아해서 그런지 문제를 보자마자 dp인것 같았다.

알고리즘 문제를 풀 때는 문제를 잘 읽어야 한다. 문제에서 요구하는 조건들을 잘 파악해야 한다.

근데 그러지 못했고, 그게 정답을 맞추지 못하는 결정적인 역할을 했다.

이거 때문에 몇 시간은 더 걸려서 풀었다.

 

9일차도 틀린 방법으로 접근했다.

반례는 찾지 못했지만 내 방법이 틀렸다는 것을 저녁에서야 깨달았고, 두번째 풀때는 생각보다 간단하게 풀어서 당황했던 기억이 있다.

AC를 받자마자 이 문제를 이렇게까지 복잡하게 생각했구나 라는 생각이 바로 들었다.

 

10일차는 대놓고 어렵게 나왔다.

생각한 알고리즘으로는

1. Parametric Search + Segment tree

2. Prefix sum + Sliding Window

이정도로 생각했고, 하루종일 로직을 그렸는데 답은 찾지 못했다.

0시가 되자마자 풀이를 확인했고, 내가 생각한 1번 방법과 비슷했지만 코드 이해가 되지않아서 포기했다.

혹시나 솔루션을 올리신 분이 있으신가 찾아봤더니 생각보다 좋은 아이디어를 얻게되어 다음날에는 AC를 받을 수 있었다.

 

2주차 난이도는 백준 골드3 ~ 플레3 정도였던 것 같다.

그래도 2개는 맞췄으니 다행이지 않을까.... 아마............ ㅠ

 

마무리

매번 뭔가를 할때마다 아쉬움은 남는것 같다.

대회를 조금 가볍게 생각해서인지 실수가 많이 나왔었고, 그거 때문에 더 좋은 점수를 받지 못한게 아닌가 생각을 해본다.

저기 사진에 있는 제출 횟수가 부끄럽긴 하다.. ㅎㅎ 세상에 문제를 제대로 못읽지를 않나..

 

문제 중에는 백준과 비슷한 문제가 몇개 섞여있었고, 가독성이 떨어지는 문제들도 있었다.

그 부분은 분명 아쉽겠지만 새롭게 알아가는 것도 많았고, 이것 또한 경험이라고 생각한다.

본선은 넥터 24기 세션 장소 중 하나였던 엘리스랩에서 진행되는데 한번더 못가게 된것도 아쉽긴 한데 잘했어야지 ^^

그래도 1일 1백준을 하기 때문에 이정도라도 하지 않았을까 라며 긍정회로를 돌려본다. 아무튼 재밌었으니까 됐지!

 

대회를 여러번 참여하긴 했지만 엘리스 코드 챌린지처럼 장기간동안 하는 대회는 처음인것 같다.

이 문제들이 공유가 가능하다면 하나씩 포스팅해볼 생각이지만 아마 안되겠지..?

다음에도 이런 기회가 있다면 다시 도전해볼 생각이다. 그때는 부족한점을 더 보완할 수 있도록 지금처럼 꾸준히 문제를 풀어야겠다.

'잡담' 카테고리의 다른 글

2024년 8월 회고  (2) 2024.09.04
2024년 7월 회고  (2) 2024.08.01
6월 회고  (0) 2024.07.01
Nexters 24기 회고  (2) 2024.06.16
5월 회고  (1) 2024.06.07

https://www.acmicpc.net/problem/17258

 

어디서 많이 본 문제네요!

월클병에 걸려버린 욱제가 파티 인원이 T명 이상일 때만 파티에 참여한다고 합니다.

친구를 최대 K명까지 투입하여 파티에 참여하는 시간을 최대로 만들어야 하는 문제입니다.

그 친구들은 친구들을 제외한 나머지 인원이 T명 이상이면 파티를 모두 나간다고 합니다.

그래서 적절한 시기에 친구들을 투입해야 최대를 구할 수 있습니다.

 

저는 dp를 활용했고, 파티 참여 인원을 구하기 위해 누적합을 추가했습니다.

imos 기법을 활용하여 시작과 끝 지점에만 카운팅을 해주고, 마지막에 누적합을 구해줍니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 파티에 참여중인 친구가 pre명일 때 파티에 머무르는 최대 시간

dp를 이렇게 구성했지만 2차원 배열로도 푸신분이 계시더라고요..? 전 모르겠습니다

 

문제에서 생각해볼 경우들은

1. 누적합이 이미 T 이상인지

2. 이전부터 참여중인 친구들과 합쳐서 T 이상인지

3. 파티를 유지할 수 있도록 친구들이 추가될 수 있는지

이렇게 3가지가 되겠습니다.

 

누적합이 이미 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외한 인원들이 T 이상이므로 참여하고 있던 친구들은 모두 빠져나갑니다.

 

이전부터 참여중인 친구들과 합쳐서 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외하면 T보다 작으므로 참여하고 있던 친구들은 계속 참여합니다.

 

파티를 유지할 수 있도록 친구들이 추가될 수 있다면 부족한 인원을 채워줄지, 아니면 친구들을 추가하지 않고 다음 시간을 확인할 지 선택합니다.

친구들을 추가한다면 +1을 해주고, 둘중 최대를 구합니다.

친구를 추가할 수 없다면 다음 시간을 보는것 밖에 없습니다.

 

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int dp[MAX][MAX][MAX];
int sum[MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx == N + 1) return 0;
 
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] >= T) {
        return ret = solve(idx + 1, k, 0) + 1;
    }
    if (sum[idx] + pre >= T) {
        return ret = solve(idx + 1, k, pre) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - (sum[idx] + pre);
    if (tmp <= k) {
        ret = max(ret, solve(idx + 1, k - tmp, pre + tmp) + 1);
    }
    return ret;
}
 
void init() {
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i < MAX; i++) {
        sum[i] += sum[i - 1];
    }
}
 
void func() {
    init();
    cout << solve(1, K, 0) << '\n';
}
 
void input() {
    int l, r;
    cin >> N >> M >> K >> T;
    while (M--) {
        cin >> l >> r;
        sum[l]++;
        sum[r]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 19623 회의실 배정 4  (0) 2024.07.29
boj 30461 낚시  (0) 2024.07.28
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

https://www.acmicpc.net/problem/30893

 

처음 이문제에 접근했을때 문제를 이해하는데 진짜 오래걸렸던 기억이 있어서 다시 풀어봤습니다.

다행히도 백준에 실려있는 문제는 설명이 잘되어있어서 이해하기가 수월하더라고요! 물론 두번째 보는거라 그런거긴 한데

그래도 확실히 게임이론은 어려운것 같습니다..

 

이 문제는 S에서 출발하여 말을 한번씩 번갈아가면서 옮길 수 있고, E에 먼저 도착하는 사람이 이기는 게임으로 선공을 할지, 후공을 할지 구하는 문제입니다.

dfs를 통해서 문제를 접근했고, E에 도착하면 true를 리턴해줍니다.

그다음 자식 노드들 중에서 true인 경우가 하나라도 있으면 true를 리턴해주시면 됩니다

 

"더는 말을 움직일 수 없게 되면 게임이 종료됩니다."

라는 말이 문제에 명시되어 있어서 상대가 자식노드가 없는 정점으로 보내버린다면 게임을 지게됩니다.

이 예외까지 생각하여 true를 최종으로 리턴받는다면 선공을, 아니면 후공을 선택하도록 합니다.

 

 

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 <vector>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
bool visit[MAX];
int N, S, E, ret;
 
bool dfs(int v, int t) {
    if (v == E) return true;
    visit[v] = true;
 
    int cnt = 0;
    bool flag = false;
    for (auto next : graph[v]) {
        if (visit[next]) continue;
        flag |= dfs(next, 1 - t);
        cnt++;
    }
    if (t && cnt > 1) return false;
 
    return flag;
}
 
void func() {
    if (dfs(S, 0)) cout << "First\n";
    else cout << "Second\n";
}
 
void input() {
    int u, v;
    cin >> N >> S >> E;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 19542 전단지 돌리기  (0) 2024.06.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

https://www.acmicpc.net/problem/22944

 

1. 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다. 
2. 이동한 곳이 안전지대라면 반복을 종료한다.
3. 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.

     버린 우산은 더 이상 사용할 수 없다.
4. 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
5. 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
6. 만약 체력이 0이 되면 죽는다.
7. 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.

 

격자 내 움직임은 위와 같은 순서로 진행됩니다.

S에서 출발하여 안전지대인 E로 도착하는 최소 거리를 구하는 문제입니다.

그리고 S에도 출발하는 직후부터는 비가 내린다고 명시되어 있습니다.

현재 체력 H와 우산의 내구도 D가 주어지며, 격자 내에는 우산이 놓여진 곳이 있습니다.

 

우선 최소거리를 구하기 위해 bfs를 사용합니다.

그리고 다음 좌표를 이동할 수 있는지 확인합니다.

내구도 1 이상인 U인 지점은 우산이 있고, 도착 지점인 E는 비가 오지 않으므로 무조건 지나갈 수 있습니다.

나머지 지점은 비가 오기 때문에 체력이 1보다는 많아야 지나갈 수 있습니다. (정확하게는 체력 + 들고 있는 우산의 남은 내구도)

 

U가 있는 지점에 도착한다면 우산의 내구도를 D로 초기화 해주시고, E가 아닌 모든 지점에서 우산의 내구도 or 체력을 1씩 감소시킵니다.

그리고 남은 체력 + 들고있는 우산의 내구도가 visit[nx][ny]보다 큰지 비교합니다.

해당 지점을 방문했더라도 체력의 상태가 다르기 때문에 방문처리를 int로 하게 되었습니다.

visit[nx][ny] >= nh + nu이면, 이전 단계보다 좋지 않은 조건으로 이동하는거라 제외를 시켜주시면 되고, 해당 visit 배열을 더 큰 값으로 갱신시켜주도록 합니다.

(중간에 체력이 0이 되었어도 visit 배열 자체가 0으로 초기화되어 있기 때문에 자동으로 걸러집니다.)

 

이 과정을 반복하여 E에 도착했다면 t를 리턴시켜주고, 반복문이 종료되어도 답을 구하지 못했다면 지나갈 수 없다는 뜻이므로 -1을 리턴해줍니다.

 

 

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
#define MAX 501
using namespace std;
typedef pair<int, int> pii;
 
char list[MAX][MAX];
int visit[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, H, D;
int sx, sy;
 
bool isMove(int x, int y, int hd) {
    if (list[x][y] == 'U' || list[x][y] == 'E') return true;
    return hd > 1;
}
 
int bfs() {
    queue<pair<pii, pii> > q;
    q.push({ {H, 0}, {sx, sy} });
    visit[sx][sy] = H;
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().second.first;
            int y = q.front().second.second;
            int h = q.front().first.first;
            int u = q.front().first.second;
            q.pop();
 
            if (list[x][y] == 'E') {
                return t;
            }
 
            for (int d = 0; d < 4; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
                int nh = h;
                int nu = u;
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (!isMove(nx, ny, h + u)) continue;
                
                if (list[nx][ny] == 'U') {
                    nu = D;
                }
                if (list[nx][ny] != 'E') {
                    if (nu) nu--;
                    else nh--;
                }
                if (visit[nx][ny] >= nh + nu) continue;
 
                q.push({ {nh, nu}, {nx,ny} });
                visit[nx][ny] = nh + nu;
            }
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs() << '\n';
}
 
void input() {
    cin >> N >> H >> D;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        for (int j = 0; j < N; j++) {
            if (list[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 27211 도넛 행성  (2) 2024.07.17
boj 19940 피자 오븐  (0) 2024.07.16
boj 2310 어드벤처 게임  (0) 2024.06.25
boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21

https://www.acmicpc.net/problem/27211

 

정말 흔한 bfs문제로 영역 구하기입니다.

list[i][j] = 0인 좌표들을 bfs를 통해 인접해있는 영역의 갯수를 구하면 됩니다.

거기에 추가로 다음 좌표가 맵 밖으로 벗어난다면 반대쪽 끝으로만 이동시켜주면 이 문제를 쉽게 해결할 수 있습니다.

 

 

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
#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;
typedef pair<int, int> pii;
 
int list[MAX][MAX];
bool visit[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M;
 
void bfs(int sx, int sy) {
    queue<pii> q;
    q.push({ sx, sy });
    visit[sx][sy] = true;
    while (!q.empty()) {
        auto xy = q.front();
        q.pop();
 
        for (int d = 0; d < 4; d++) {
            int nx = xy.first + direct[d][0];
            int ny = xy.second + direct[d][1];
 
            if (nx < 0) nx = N - 1;
            if (ny < 0) ny = M - 1;
            if (nx >= N) nx = 0;
            if (ny >= M) ny = 0;
            if (visit[nx][ny] || list[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j] || list[i][j]) continue;
            ret++;
            bfs(i, j);
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 22944 죽음의 비  (0) 2024.07.18
boj 19940 피자 오븐  (0) 2024.07.16
boj 2310 어드벤처 게임  (0) 2024.06.25
boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21

https://www.acmicpc.net/problem/19940

 

처음 이문제를 봤을때 N의 범위가 10000000이라 set을 써야하나 고민했었습니다.

근데 한 번에 이동할 수 있는건 (+60, +10, -10, +1, -1) 이렇게 5개밖에 없기 때문에 언제 1000만을 찍나 고민했습니다.

일단 바로 알수있는건 N이 클수록 +60을 많이 누르는게 이득이지 않을까 생각하여 bfs에 greedy까지 생각하게 되었습니다.

 

여기까지 오셨다면 문제를 쉽게 해결할 수 있습니다.

N을 60으로 나눈다면 우리가 할건  0 ~ 59까지의 최소 횟수만 구하면 됩니다.

방문처리는 N에 대해서만 해주시면 되고, queue에는 N과 버튼 누른 횟수를 모두 넣어줬습니다.

문제에서 횟수가 동일하다면 (-1 > +1 > -10 > +10 > +60) 순으로 높은 우선순위를 부여한다고 명시되어 있기 때문에

연산의 순서 또한 (-1 -> +1 -> -10 -> +10 -> +60) 으로 진행합니다.

다음에는 N을 입력받고, +60에는 N / 60을 더해주고, 나머지는 미리 구했던 값을 그대로 출력해주시면 되겠습니다.

 

개인적으로 이 문제 어렵다고 느껴졌는데 골드5 더라고요..?

난이도 기여하러 갔더니 다들 쉽다는 반응은 아니었는데 골드5를 주셨더라고요..??

난 어렵게 느껴졌는데.. 골드4보다 더 주고싶었는데.. 그냥 그렇다고요..

 

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 61
using namespace std;
 
bool visit[MAX];
int btns[5] = { 60, 10, -10, 1, -1 };
vector<int> ret[MAX];
int N;
 
void bfs() {
    queue<pair<int, vector<int>> > q;
    ret[0] = vector<int>(5, 0);
    q.push({ 0,ret[0] });
    visit[0] = true;
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
 
        for (int d = 4; d >= 0; d--) {
            int next = now.first + btns[d];
            if (next < 0 || next > 60) continue;
            if (visit[next]) continue;
 
            visit[next] = true;
            ret[next] = now.second;
            ret[next][d]++;
            q.push({ next, ret[next] });
        }
    }
}
 
void func() {
    int x = N / 60;
    int y = N % 60;
    cout << x + ret[y][0] << ' ' << ret[y][1] << ' ' << ret[y][2] << ' ' << ret[y][3] << ' ' << ret[y][4] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    bfs();
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

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

boj 22944 죽음의 비  (0) 2024.07.18
boj 27211 도넛 행성  (2) 2024.07.17
boj 2310 어드벤처 게임  (0) 2024.06.25
boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21

+ Recent posts

티스토리툴바