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/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

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

 

13136번: Do Not Touch Anything

첫 번째 줄에 좌석의 세로 크기, 가로 크기 R, C와 한 대의 CCTV가 수용할 수 있는 범위 N이 주어진다. (1 ≤ R, C, N ≤ 1,000,000)

www.acmicpc.net

문제 이름 보자마자 icpc가 떠올랐습니다.

제가 icpc 본선 갔을때도 진행자분이 항상 "Do Not Touch Anything"을 말하곤 하셨습니다 ㅋㅋ

 

진행자분을 대신하여 cctv를 설치할건데, N * N의 범위를 감시할 수 있다고 합니다.

R / N * C / N으로 구할 수 있지만 R, C을 N으로 나눈 나머지가 존재한다면 1을 추가로 더합니다.

(나머지에 해당하는 부분을 감시할 수 없기 때문입니다.)

 

100만 * 100만은 int 범위를 초과하므로 자료형은 long 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
#include <iostream>
using namespace std;
typedef long long ll;
 
ll R, C, N;
 
void func() {
    ll x = R / N + (R % N != 0);
    ll y = C / N + (C % N != 0);
 
    cout << x * y << '\n';
}
 
void input() {
    cin >> R >> C >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1837 암호제작  (0) 2021.02.04
boj 15740 A+B - 9  (0) 2021.01.31
boj 1002 터렛  (0) 2021.01.27

+ Recent posts

티스토리툴바