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

 

N개의 정점으로 이루어진 트리에서 i < j인 정점들 사이 거리가 최소가 되도록 하려면 어떤 트리를 만들어야하는지 구하는 문제입니다.

 

트리를 직접 그려보면 Star Graph 형식이 최소가 된다는 것을 알 수 있습니다.

Star Graph는 하나의 정점에 다른 모든 정점이 연결된 형태입니다.

 

이렇게되면 1번 정점과 연결된 다른 정점은 거리가 각각 1입니다. (N - 1)

나머지 정점들끼리의 거리는 각각 2입니다.

나머지 N - 1개의 정점에서 2개를 고르는 경우의 수는 N-1C2이며, 두개 곱하면 (N - 2) * (N - 1)이 됩니다.

위에서 구한 두 수를 더하면 N - 1 + (N - 2) * (N - 1) 이라는 답을 구할 수 있습니다.

 

스페셜 저지 문제이기 때문에 기준이 되는 정점을 아무거나 고르시면 됩니다. 저는 1번 정점을 기준으로 정했습니다.

그리고 기준이 되는 정점과 i를 반복해서 출력해주시면 되겠습니다.

 

 

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
#include <iostream>
using namespace std;
typedef long long ll;
 
ll N;
 
void func() {
    cout << N - 1LL + (N - 2LL) * (N - 1LL) << '\n';
    for (int i = 2; i <= N; i++) {
        cout << "1 " << i << '\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 7982 순열 그래프의 연결성 판별  (0) 2024.08.16
boj 16161 가장 긴 증가하는 팰린드롬 부분수열  (0) 2024.08.15
boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05

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

 

순열 그래프는 N개의 정점이 1 ~ N의 번호가 하나씩 구성되어 있습니다.

그리고 두 정점 쌍 i, j (1 ≤ i < j ≤ n) 는 ai > aj 일때 간선으로 연결되어 있습니다.

4
2 3 1 4

순열이 이렇게 주어졌을 때  2, 3 > 1이므로 (1, 2), (1, 3)이 각각 연결되어 있고

(1, 2, 3) (4) 로 집합을 나눌 수 있습니다.

 

여기서 알 수 있는건 i번째 까지 순회했을때 max가 i이면 해당 위치까지 하나의 집합으로 묶을 수 있습니다.

위의 예시로 보면

3번 인덱스까지의 max가 3이므로 1, 2, 3을 집합으로 묶을 수 있고, 4번 인덱스까지의 max가 4이므로 4를 집합으로 묶을 수 있습니다.

이전 집합의 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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;
 
vector<int> v;
int list[MAX];
int N;
 
void func() {
    int maxValue = 0;
    for (int i = 1; i <= N; i++) {
        maxValue = max(maxValue, list[i]);
        if (i == maxValue) v.push_back(i);
    }
 
    int pre = 0;
    cout << v.size() << '\n';
    for (auto x : v) {
        cout << x - pre << ' ';
        for (int i = pre + 1; i <= x; i++) cout << i << ' ';
        cout << '\n';
        pre = x;
    }
}
 
void input() {
    cin >> N;
    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

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

boj 27966 △  (0) 2024.08.22
boj 16161 가장 긴 증가하는 팰린드롬 부분수열  (0) 2024.08.15
boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05

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

 

팰린드롬은 앞/뒤에서 읽었을 때 같은 수열입니다.

이 문제에서는 증가하는 팰린드롬을 구해야 합니다.

 

1, 2, 3, 4, 3, 2, 1
1, 3, 6, 7, 7, 6, 3, 1

이런것처럼 중앙으로 갈수록 값이 커지는 것이 증가하는 팰린드롬 수열입니다.

 

1, 2, 4, 3, 2, 1
4, 3, 2, 3, 4
1, 1, 1, 1

 

 

증가하는 팰린드롬이 아닌 경우는

1. 애초에 팰린드롬이 아닌 경우

2. 팰린드롬이지만 값이 증가하지 않는 경우 (값이 같아도 x)

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

 

저는 중앙을 먼저 정해놓고 한칸씩 이동하여 팰린드롬의 길이를 직접 구해봤습니다.

팰린드롬의 길이에 따라 중앙은 1개 or 2개가 될 수 있습니다.

따라서 l번째 수와 l + 1번째 수가 같으면 묶어서 중앙으로 두고 구할 수 있습니다.

이후에는 그냥 왼쪽, 오른쪽으로 한칸씩 이동하면서 증가하는 팰린드롬인지 확인해주시고, 최대 길이를 갱신해주시면 됩니다.

 

그리고 이 문제가 "증가하는 팰린드롬"이기 때문에 하나 더 생각할 수 있는건

s ~ e 범위의 팰린드롬을 찾았다고 했을 때, list[s], list[e]은 해당 팰린드롬에서 항상 가장 작은 수를 담당하고 있습니다.

그렇기 때문에 e번째 수에서 왼쪽으로 이동하더라도 큰 수가 있을 수밖에 없고, 더 큰 범위의 팰린드롬을 찾을 수 없습니다.

따라서 중앙값인 l, r을 +1씩 볼 필요 없이 s ~ e 범위의 다음 인덱스부터 다시 확인해주시면 불필요한 계산 없이 정답을 구할 수 있습니다.

 

 

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>
#define MAX 100001
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int l = 0;
    int ret = 1;
    while (l < N) {
        int r = l;
        if (r + 1 < N && list[l] == list[r + 1]) r++;
 
        int s = l - 1;
        int e = r + 1;
        while (s >= 0 && e < N) {
            if (list[s] != list[e] || list[s] >= list[s + 1]) break;
            e++;
            s--;
        }
 
        ret = max(ret, e - s - 1);
        l = e;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 27966 △  (0) 2024.08.22
boj 7982 순열 그래프의 연결성 판별  (0) 2024.08.16
boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05

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

 

N개의 돌 중에 팰린드롬 수만큼의 돌을 가져갈 수 있으며, 마지막에 모든 돌을 가져가는 사람이 이깁니다.

 

우선 1 ~ 9는 팰린드롬이므로 무조건 먼저하는 사람이 이깁니다.

N = 10이라면 1 ~ 9개를 가져가더라도 9 ~ 1개는 무조건 남기 때문에 먼저하는 사람이 집니다.

그리고 N = 11 ~ 19는 1 ~ 9를 적절하게 뺀다면 다음 사람에게 10을 넘겨줄 수 있으므로 무조건 이길 수 있습니다.

이런식으로 간다면 10의 배수가 아닐때는 무조건 선공이 이긴다는 것을 알 수 있습니다.

0으로 시작하는 수는 없으므로 10의 배수는 팰린드롬이 올 수 없으므로 다른건 고려하지 않아도 됩니다.

 

 

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 <iostream>
using namespace std;
typedef long long ll;
 
ll N;
 
void func() {
    if (N % 10) cout << "0\n";
    else cout << "1\n";
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

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

boj 7982 순열 그래프의 연결성 판별  (0) 2024.08.16
boj 16161 가장 긴 증가하는 팰린드롬 부분수열  (0) 2024.08.15
boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05
boj 10350 Banks  (0) 2024.07.31

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

 

안그래도 문자열에 약한데 애드혹까지 섞이니 뇌정지가 오는 문제였습니다.

우선 문자열이 섞여있는 채로 저장되어있고,  문자열이 어떤 수들로 구성되어 있는지 파악해야 합니다.

그러면 각 숫자들의 고유한 알파벳을 구해서 카운팅하는 방법을 떠올릴 수 있습니다.

 

0 2 4 6 8은 각각 고유한 알파벳이 있습니다.

0 - Z

2 - W

4 - U

6 - X

8 - G

 

그리고 이들을 제외한 숫자들 중 고유한 알파벳을 뽑으면

3 - H

5 - F

7 - S

9 - I

1 - O

순서대로 이렇게 가져올 수 있습니다.

 

먼저 입력으로 들어온 문자열의 문자들을 모두 카운팅합니다.

이후 위에서 구한 알파벳을 순서대로 가져와서 카운팅을 빼주면서 정답을 구하는 방식으로 구현했습니다.

 

 

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 <string>
#include <cstring>
#define MAX 10
using namespace std;
 
string str;
string alpha[MAX] = { "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" };
pair<int, char> ch[MAX] = { {0,'Z'}, {2,'W'}, {4, 'U'}, {6, 'X'}, {8, 'G'}, {3,'H'}, {5, 'F'}, {7, 'S'}, {9, 'I'}, {1,'O'} };
int alphaCnt[26];
int cnt[MAX];
int len;
 
void solve() {
    for (auto c : ch) {
        while (alphaCnt[c.second - 'A']) {
            cnt[c.first]++;
            for (auto a : alpha[c.first]) {
                alphaCnt[a - 'A']--;
            }
        }
    }
}
 
void func(int tc) {
    for (auto x : str) {
        alphaCnt[x - 'A']++;
    }
    solve();
 
    cout << "Case #" << tc << ": ";
    for (int i = 0; i < MAX; i++) {
        while (cnt[i]--) {
            cout << i;
        }
    }
    cout << '\n';
}
 
void input() {
    cin >> str;
    len = str.size();
}
 
void init() {
    memset(cnt, 0, sizeof(cnt));
    memset(alphaCnt, 0, sizeof(alphaCnt));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        input();
        func(t);
        init();
    }
 
    return 0;
}
 cs

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

boj 16161 가장 긴 증가하는 팰린드롬 부분수열  (0) 2024.08.15
boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 21316 스피카  (0) 2024.08.05
boj 10350 Banks  (0) 2024.07.31
boj 5527 전구 장식  (0) 2024.07.30

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

 

12개 간선이 입력으로 주어지고, 어떤 입력이든 이 모양으로 주어진다고 합니다.

여기서 Spica가 되는 정점의 조건은 주변 정점들과 간선들로 알아낼 수 있습니다.

 

저는 Spica에 인접한 정점들은 각각 1, 2, 3개의 간선이 있다는 것을 파악했고, 그대로 구현했습니다.

1, 2, 3개는 각각 비트마스킹을 활용했습니다.

 

 

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
#include <iostream>
#include <vector>
#define MAX 13
using namespace std;
 
vector<int> v[MAX];
 
void func() {
    for (int i = 1; i < MAX; i++) {
        int flag = 0;
        for (auto next : v[i]) {
            flag |= (1 << (v[next].size() - 1));
        }
 
        if (flag == 7) {
            cout << i << '\n';
            return;
        }
    }
}
 
void input() {
    int x, y;
    for (int i = 1; i < MAX; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 24553 팰린드롬 게임  (0) 2024.08.07
boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 10350 Banks  (0) 2024.07.31
boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26

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

 

특정 범위의 전구 상태를 뒤집는 기계를 1번만 사용하여 연속된 교대 패턴의 최대 크기를 구하는 문제입니다.

교대 패턴은 말 그대로 인접한 전구의 상태가 다른 패턴입니다. 1 0 1 0 1 이나 0 1 0 1같은 패턴입니다.

 

dp를 활용하여 특정 범위를 뒤집으면서 할 수도 있겠지만 다른 방법으로 쉽게 풀렸습니다.

1 1 0 0 1 0 1 1 1 0

입력이 이렇게 주어졌을때 각 교대패턴의 크기를 구하면

1 2 4 1 2 이렇게 됩니다.

그렇다면 여기서 한 구간을 뒤집게 되면 왼쪽과 오른쪽에 인접한 구간과 하나의 패턴으로 합쳐질 수 있습니다.

 

각 교대 패턴이 1 0 / 0 1 0 1 / 1

이렇게 되어있다고 했을때 0 1 0 1을 뒤집어주면 1 0 1 0이 됩니다.

그러면 전구들의 상태는 1 0 / 1 0 1 0 / 1 이렇게 되므로 세 구간은 하나로 합쳐지고, 크기는 7이 됩니다.

즉 연속된 3개 패턴 크기의 합의 최댓값을 구해주시면 답을 구하실 수 있습니다.

물론 패턴의 갯수가 3개보다 작으면 그 패턴 크기의 합을 구해주시면 됩니다.

 

 

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
#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
 
vector<int> v;
int list[MAX];
int N;
 
void init() {
    int pre = list[0];
    int cnt = 1;
    for (int i = 1; i < N; i++) {
        if (pre == list[i]) {
            v.push_back(cnt);
            cnt = 1;
        }
        else {
            cnt++;
        }
        pre = list[i];
    }
    v.push_back(cnt);
}
 
void func() {
    init();
 
    int ret = 0;
    if (v.size() < 3) {
        for (auto x : v) {
            ret += x;
        }
    }
    else {
        for (int i = 1; i < v.size() - 1; i++) {
            ret = max(ret, v[i - 1] + v[i] + v[i + 1]);
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 21316 스피카  (0) 2024.08.05
boj 10350 Banks  (0) 2024.07.31
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25
boj 14675 단절점과 단절선  (0) 2024.07.23

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

 

순서쌍 (x, y)는 학생y 가 학생x 보다 뒤에 있으면서 더 작은 번호를 가지고 있다는 것을 의미하며,

입력으로 주어지는 순서쌍을 제외하면 더 작은 번호를 갖고있는 학생은 무조건 앞에 있다는 뜻이 됩니다.

 

그러면 최초 입력을 받기 전에는 1 ~ N번째 학생은 1 ~ N번을 순서대로 들고있게 됩니다.

그리고 입력되는 (x, y)에서 x는 본인보다 뒤에 있는 y보다 큰 수를 갖고 있으므로 +1으로 카운팅할 수 있습니다.

반대로 y는 -1으로 카운팅할 수 있습니다.

 

그렇게 수정된 배열에는 학생들이 들고있는 번호가 완성되지만 중복이 포함될 수 있습니다.

그런 경우에는 -1을 출력해주시고, 그렇지 않다면 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#define MAX 100001
using namespace std;
 
int list[MAX];
bool chk[MAX];
int N, M;
 
void init() {
    for (int i = 1; i <= N; i++) {
        list[i] = i;
    }
}
 
void func() {
    for (int i = 1; i <= N; i++) {
        if (chk[list[i]]) {
            cout << "-1\n";
            return;
        }
        chk[list[i]] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        cout << list[i] << ' ';
    }
    cout << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> M;
    init();
    while (M--) {
        cin >> x >> y;
        list[x]++;
        list[y]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 10350 Banks  (0) 2024.07.31
boj 5527 전구 장식  (0) 2024.07.30
boj 2381 최대 거리  (0) 2024.07.25
boj 14675 단절점과 단절선  (0) 2024.07.23
boj 27468 2배 또는 0.5배  (0) 2024.07.22

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

 

두 점의 좌표 (a, b), (c, d)가 있을 때 L1-metric 거리는 |a - c| + |b - d| 이라고 하고 L1-metric의 최댓값을 구하는 문제입니다.

우선 절댓값부터 전개를 하면

1. (a + b) - (c + d)

2. - (a + b) + (c + d)

3. (a - b) - (c - d)

4. - (a - b) + (c - d)

이렇게 되는것을 알 수 있습니다.

 

여기서 (1, 2), (3, 4)를 묶어서 보면 각각 x + y, x - y의 차이를 계산하고 있습니다.

그렇다면 x + y, x - y를 배열에 각각 넣고 정렬해서 최대 - 최소를 구한다면 답을 구할 수 있습니다.

이 때 x + y의 최대 - 최소, x - y의 최대 - 최소 중 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
#include <iostream>
#include <algorithm>
#define MAX 50001
using namespace std;
 
int list[2][MAX];
int N;
 
void func() {
    sort(list[0], list[0] + N);
    sort(list[1], list[1] + N);
    cout << max(list[0][N - 1] - list[0][0], list[1][N - 1] - list[1][0]) << '\n';
}
 
void input() {
    int x, y;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        list[0][i] = x + y;
        list[1][i] = x - y;
    }
}
 
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 14675 단절점과 단절선  (0) 2024.07.23
boj 27468 2배 또는 0.5배  (0) 2024.07.22
boj 1377 버블 소트  (0) 2024.06.07

문제

 

풀이

처음 이 문제를 봤을때 손도 못댔었는데 정답 코드를 보니 조금 허무했습니다.

이런게 애드혹이겠죠.. ㅠ

 

우선 N의 범위가 10^7이기 때문에 범위 내에서는 8종류의 수까지 표현할 수 있습니다.

따라서 K가 9, 10인 경우에는 9, 10종류의 수를 사용한 가장 작은수를 출력하면 그게 답입니다.

K = 9일 때는102345678이 되겠고, K = 10일 때는 1023456789가 되겠습니다.

 

그러면 나머지의 경우는 많아봐야 1천만 정도라서 N을 1씩 증가시키면서 직접 비교해도 시간 안에 문제를 해결할 수 있습니다.

저는 N + 1을 문자열로 만들어서 각 자리를 카운팅한 다음 카운팅한 갯수가 정확이 K개인지 확인하는 방식으로 구현했습니다.

N + 1을 계속 하기때문에 무조건 N보다는 큰 숫자일 수밖에 없고, 그 수가 정확이 K개의 숫자만 사용했다면 그게 정답이 됩니다.

 

코드

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
string str;
int K;
bool chk[10];
 
void func() {
    if (K == 10) {
        cout << "1023456789\n";
        return;
    }
    if (K == 9) {
        cout << "102345678\n";
        return;
    }
 
    while (1) {
        str = to_string(stoi(str) + 1);
        int cnt = 0;
        for (auto x : str) {
            if (chk[x - '0']) continue;
            cnt++;
            chk[x - '0'] = true;
        }
 
        if (cnt == K) {
            cout << str << '\n';
            return;
        }
 
        memset(chk, false, sizeof(chk));
    }
}
 
void input() {
    cin >> str >> K;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

엘리스 코드 챌린지 Day 9 격자 위의 ELICE  (0) 2024.07.24
엘리스 코드 챌린지 Day 8 강림제  (0) 2024.07.23
엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22

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

 

단절점은 지웠을 때 그래프가 2개 이상으로 나눠지는 정점이라고 하고,

단절선은 지웠을 때 그래프가 2개 이상으로 나눠지는 간선이라고 합니다.

 

이 문제는 트리라고 명시되어 있기 때문에 애드혹으로 접근할 수 있습니다.

트리는 N - 1개의 간선만으로 N개의 정점을 연결하는 그래프입니다.

즉, 그래프에서 간선을 최소 갯수로 사용한게 트리입니다.

 

그렇다면 간선이 하나라도 없어진다면 더이상 하나의 그래프가 될 수 없습니다.

그러면 type == 2일 경우는 모두 yes를 출력하는걸로 마무리할 수 있습니다.

 

그 다음은 단절점인데

간선이 1개인 정점을 지우게 되더라도 여전히 하나의 그래프가 남게됩니다.

간선이 2개 이상인 정점을 지우게 되면 그 간선 만큼 2개 이상의 그래프로 나뉘는것을 알 수 있습니다.

 

그러면 정점을 지우면 해당 정점에 연결된 간선만큼 그래프가 나뉜다는 것을 알 수 있고,

type == 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
#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
 
int cnt[MAX];
int N, M;
 
void func() {
    int type, x;
    while (M--) {
        cin >> type >> x;
        if (type == 1) {
            if (cnt[x] > 1) cout << "yes\n";
            else cout << "no\n";
        }
        else cout << "yes\n";
    }
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        cnt[u]++;
        cnt[v]++;
    }
    cin >> M;
}
 
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 27468 2배 또는 0.5배  (0) 2024.07.22
boj 1377 버블 소트  (0) 2024.06.07

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

+ Recent posts

티스토리툴바