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

 

1837번: 암호제작

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로

www.acmicpc.net

BigInteger를 사용하는 문제입니다.

P는 소수의 곱으로 이루어져있지만 10^100이라는 수가 입력으로 주어집니다.

K는 P가 좋은 암호인지, 좋지 않은 암호인지 구별하는 수이며 1000000까지 주어집니다.

 

P를 나타내는 소수 p, q 중에 하나라도 K보다 작으면 이 암호P는 좋지 않은 암호입니다.

하지만 P가 너무 큰 수이기 때문에 소수를 직접 구할 수 없으므로 K범위 내의 소수를 모두 구하여

 

구한 소수들 중 P와 나머지 연산을 해서 0이 되는 수가 있으면 BAD, 없으면 GOOD를 출력하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static BigInteger P, K;
    static boolean sosuchk[] = new boolean[1000001];
    static Set<BigInteger> sosu = new TreeSet<>();
    static int k;
 
    static void func() {
        Iterator<BigInteger> iter = sosu.iterator();
        while (iter.hasNext()) {
            BigInteger a = iter.next();
            if (a.compareTo(K) >= 0)
                break;
 
            if (P.mod(a).equals(new BigInteger("0"))) {
                System.out.println("BAD " + a);
                return;
            }
        }
 
        System.out.println("GOOD");
    }
 
    static void init() {
        for (int i = 2; i <= 1000000; i++) {
            if (sosuchk[i])
                continue;
 
            sosu.add(new BigInteger(Integer.toString(i)));
            for (int j = 2; i * j <= 1000000; j++) {
                if (sosuchk[i * j])
                    continue;
 
                sosuchk[i * j] = true;
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        P = new BigInteger(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        K = new BigInteger(Integer.toString(k));
    }
 
    public static void main(String[] args) throws Exception {
        init();
        input();
        func();
    }
}
 cs

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

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 15740 A+B - 9  (0) 2021.01.31
boj 1002 터렛  (0) 2021.01.27

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

티스토리툴바