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

www.acmicpc.net/problem/8320

 

8320번: 직사각형을 만드는 방법

상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수

www.acmicpc.net

길이가 1인 정사각형 N개를 가지고 만들 수 있는 직사각형의 갯수를 구하는 문제입니다.

이 때, N개를 모두 사용하지 않아도 됩니다.

 

저는 N개로 만들 수 있는 높이(i)가 1인 직사각형부터 높이를 1씩 늘려가며 갯수를 구하였습니다.

그럼 너비(j)는 i * j <= N 인 경우의 갯수를 세어주시면 됩니다.

 

N = 6일 때를 예로 들면

높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6

높이가 2일 때 가능한 너비 => 1, 2, 3

높이가 3일 때 가능한 너비 => 1, 2

높이가 4일 때 가능한 너비 => 1

높이가 5일 때 가능한 너비 => 1

높이가 6일 때 가능한 너비 => 1

답 14??

이렇게 구할수 있지만 문제에는 직사각형 A를 회전시켜서 B를 만들 수 있는 경우

즉, (i * j)이나 (j * i)이나 같은 직사각형으로 본다는 것입니다. 그러면 중복체크를 해야합니다.

 

그러면

높이가 1일 때 가능한 너비 => 1, 2, 3, 4, 5, 6

높이가 2일 때 가능한 너비 => 2, 3

답 8

 

이렇게 축소를 시킬 수 있습니다.

여기서 찾은 규칙성이 높이는 1부터 sqrt(N)까지, 너비는 i부터 i * j <= 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
#include <iostream>
#include <cmath>
using namespace std;
 
int N;
 
void func() {
    int ans = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        for (int j = i; i * j <= N; j++) {
            ans++;
        }
    }
 
    cout << ans << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    func();
 
    return 0;
}
 cs

 

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

boj 16719 ZOAC  (0) 2021.03.15
boj 3085 사탕 게임  (0) 2021.02.26
boj 3985 롤 케이크  (0) 2021.02.25
boj 2116 주사위 쌓기  (0) 2021.02.25
boj 10163 색종이  (0) 2021.02.24

www.acmicpc.net/problem/15740

 

15740번: A+B - 9

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

자바 공부하다가 BigInteger라는 객체가 있는걸 알았습니다..

존재를 까먹기 전에 포스팅이라도 하려고 급하게 문제를 풀었습니다..

 

이 문제는 A+B를 출력하는 매우 간단한 문제이지만 입력으로 주어지는 수가 -10^10000 ~ 10^10000이라서

int, long으로는 해결할 수 없습니다. 그래서 BigInteger를 사용해야 합니다.

BigInteger는 일반적인 +, -와 같은 연산은 불가능하며,

add(덧셈), subtract(뺄셈), multiply(곱셈), divide(나눗셈), remainder(나머지)와 같은 내부 메소드를 사용해야합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static BigInteger A, B;
    
    static void input() throws Exception{
        st = new StringTokenizer(br.readLine());
        
        A = new BigInteger(st.nextToken());
        B = new BigInteger(st.nextToken());
    }
    
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(A.add(B));
    }
}
 cs

 

 

 

 

 

그리고... 파이썬 코드입니다.

1
2
3
4
x, y = input().split()
x = int(x)
y = int(y)
print(x + y)
 cs

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

너무 간단한데요;;

 

C++로 BigInteger를 직접 구현했던 때가 기억이 납니다 ㅎㅎ;;

 

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

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 1837 암호제작  (0) 2021.02.04
boj 1002 터렛  (0) 2021.01.27

www.acmicpc.net/problem/1002

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

이 문제는 두 사람의 위치와 그 위치에서 각각 보이는 적까지의 거리가 주어지며 수학적 지식이 필요한 문제입니다.

저는 원의 반지름과 두 점 사이의 거리를 이용하여 해결하였습니다.

 

A의 좌표가 주어지고, A가 계산한 적까지의 거리를 반지름이라고 생각하시면 됩니다.

B도 같은 방법으로 하면 두개의 원이 그려집니다.

그러면 이 문제는 두 원의 접점의 갯수를 구하는 문제가 됩니다.

두 원이 접하는 경우는 두가지인데 외접과 내접 모두 생각을 해야합니다.

 

두 점 사이의 거리 = d

A의 반지름 = r1 (더 짧은 반지름)

B의 반지름 = r2 (더 긴 반지름)

라고 하였을 때

 

d > r1 + r2    ->    접하지 않으므로 0개

d == r1 + r2  ->    접점이 1개(외접)

d < r1 + r2    ->    접점이 2개이거나 내접여부 확인

 

d + r1 == r2  ->    접점이 1개(내접)

d + r1 > r2    ->    접점이 2개

나머지 -> 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
 
    static class Circle {
        double x;
        double y;
        double r;
    }
 
    static Circle A, B;
    static double d;
    static int ans;
 
    static void swap() {
        Circle tmp = A;
        A = B;
        B = tmp;
    }
 
    static void func() {
        if (A.r > B.r) {
            swap();
        }
 
        if (A.x == B.x && A.y == B.y && A.r == B.r)
            ans = -1;
        else if (d == A.r + B.r)
            ans = 1;
        else if (d > A.r + B.r)
            ans = 0;
        else {
            if (d + A.r == B.r)
                ans = 1;
            else if (d + A.r > B.r)
                ans = 2;
            else
                ans = 0;
        }
    }
 
    static void print() {
        sb.append(ans + "\n");
        ans = 0;
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        A.x = Double.parseDouble(st.nextToken());
        A.y = Double.parseDouble(st.nextToken());
        A.r = Double.parseDouble(st.nextToken());
        
        B.x = Double.parseDouble(st.nextToken());
        B.y = Double.parseDouble(st.nextToken());
        B.r = Double.parseDouble(st.nextToken());
        d = Math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            A = new Circle();
            B = new Circle();
            input();
            func();
            print();
        }
        System.out.println(sb.toString());
    }
}
 cs

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

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 1837 암호제작  (0) 2021.02.04
boj 15740 A+B - 9  (0) 2021.01.31

+ Recent posts

티스토리툴바