더 이상 물러설 곳이 없다

www.acmicpc.net/problem/2089

문제

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 10진법으로 표현된 수 N이 주어진다.

출력

-2진법 수를 출력한다.

제한

• -2,000,000,000 ≤ N ≤ 2,000,000,000

예제 입력 1

-13

예제 출력 1

110111

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n == 0) {
            System.out.println(0);
            return;
        }

        int[] arr = new int[100];
        int idx = -1;
        while(n != 1) {
            if(n < 0) {
                if((n*-1) % 2 == 1) {  // 음홀
                    n = n / -2 + 1;
                    arr[++idx] = 1;
                }else {  // 음짝
                    n = n / -2;
                    arr[++idx] = 0;
                }
            }else {
                if(n % 2 == 1) {  // 양홀
                    n = n / -2;
                    arr[++idx] = 1;
                }else {  // 양짝
                    n = n / -2;
                    arr[++idx] = 0;
                }
            }
        }
        arr[++idx] = 1;
        for(int i = idx; i >= 0; i--) {
            System.out.print(arr[i]);
        }
    }
}

양수 홀짝, 음수 홀짝 경우를 나누어 계산해야 한다.

예제 입력을 손으로 풀어보고 그에 맞추어서 짜자.

www.acmicpc.net/problem/1212

문제

8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.

출력

첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다.

예제 입력 1

314

예제 출력 1

11001100

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();

        String[] binary = {"000", "001", "010", "011", "100", "101", "110", "111"};
        for(int i = 0; i < n.length(); i++) {
            int octa = n.charAt(i) - '0';
            String bin = binary[octa];

            if(i == 0) {
                if(bin.startsWith("000")) {
                    System.out.print("0");
                }else if(bin.startsWith("00")) {
                    System.out.print(bin.charAt(2));
                }else if(bin.startsWith("0")) {
                    System.out.print(bin.charAt(1));
                    System.out.print(bin.charAt(2));
                }else {
                    System.out.print(bin);
                }

            }else {
                System.out.print(bin);
            }
        }
    }
}

www.acmicpc.net/problem/1373

문제

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 주어진 수를 8진수로 변환하여 출력한다.

예제 입력 1

11001100

예제 출력 1

314

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();

        if(n.length() % 3 == 1) {
            n = "00" + n;
        }else if(n.length() % 3 == 2) {
            n = "0" + n;
        }

        ArrayList<Integer> binaryList = new ArrayList<>();
        for(int i = n.length() - 1; i >= 0; i--) {
            binaryList.add(n.charAt(i) - '0');
        }

        ArrayList<Integer> octaList = new ArrayList<>();
        for(int i = 0; i < binaryList.size(); i+=3) {
            int octa = binaryList.get(i) * (int)Math.pow(2, 0);
            octa += binaryList.get(i+1) * (int)Math.pow(2, 1);
            octa += binaryList.get(i+2) * (int)Math.pow(2, 2);
            octaList.add(octa) ;
        }
        Collections.reverse(octaList);

        for(int octa : octaList) {
            System.out.print(octa);
        }
    }
}

mod 3에 따라 String의 길이를 늘려주고 시작하는 게 핵심

www.acmicpc.net/problem/2745

문제

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

예제 입력 1

ZZZZZ 36

예제 출력 1

60466175

풀이 .

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        String N = st.nextToken();
        int B = Integer.parseInt(st.nextToken());

        ArrayList<Character> cList = new ArrayList<>();
        for(int i = N.length() - 1; i >= 0; i--) {
            cList.add(N.charAt(i));
        }

        int decimal = 0;
        for(int i = 0; i < cList.size(); i++) {
            int num = 0;
            char ch = cList.get(i);
            if('0' <= ch && ch <= '9') {
                num = ch - '0';
            }else {
                num = ch - 55;
            }
            decimal += num * Math.pow(B, i);
        }
        System.out.println(decimal);
    }
}

www.acmicpc.net/problem/11005

문제

10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다.

출력

첫째 줄에 10진법 수 N을 B진법으로 출력한다.

예제 입력 1

60466175 36

예제 출력 1

ZZZZZ

풀이 .

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // A ~ Z : 65 ~ 90
        char[] arr = new char[36];
        for(int i = 0; i <= 35; i++) {
            if(i < 10) {
                arr[i] = (char)(i + '0');
            }else {
                arr[i] = (char)(i + 55);
            }
        }

        ArrayList<Integer> list = new ArrayList<>();
        while(N != 0) {
            int mod = N % B;
            list.add(mod);
            N = N / B;
        }
        Collections.reverse(list);

        for(int mod : list) {
            sb.append(arr[mod]);
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

그냥 구현하면 된다.

www.acmicpc.net/problem/9613

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

3

4 10 20 30 40

3 7 5 12

3 125 15 25

예제 출력 1

70

3

35

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int gcd(int a, int b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            for(int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            long sum = 0;
            for(int i = 0; i < n - 1; i++) {
                for(int j = i + 1; j < n; j++) {
                    sum += gcd(arr[i], arr[j]);
                }
            }
            System.out.println(sum);
        }
    }
}

총 n^2 (100^2 = 10^4) 개의 GCD가 나올 수 있고 그 최대값은 10^6이다.

sum의 최대값은 10^10 이므로 long을 써야 한다.

www.acmicpc.net/problem/1850

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

예제 입력 1

3 4

예제 출력 1

1

예제 입력 2

3 6

예제 출력 2

111

예제 입력 3

500000000000000000 500000000000000002

예제 출력 3

11

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long gcd = gcd(a, b);
        for(int i = 0; i < gcd; i++) {
            sb.append("1");
        }
        System.out.println(sb.toString());
    }
}

함정이다.

입력받은 1의 개수만큼 1을 이어붙인 숫자를 만들어서 GCD를 구하려고 했다.

이렇게 하려면 예제 입력 3번의 경우에는 도저히 숫자를 만들어낼 수가 없다.
(50경자리 숫자를 어떻게 만들어..)

정답 코드를 찾아보니,

1의 개수끼리 GCD를 구하면 그게 그 수의 GCD에 들어있는 1의 개수가 된단다.

왜인지는 모르겠다. 편하게 이해하기엔 수학적 머리가 너무 딸린다.

알고 싶지도 않다.

www.acmicpc.net/problem/1934

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

3

1 45000

6 10

13 17

예제 출력 1

45000

30

221

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int gcd(int a, int b) {  // 최대공약수
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int gcd = gcd(a, b);
            int lcm = (a * b) / gcd;
            System.out.println(lcm);
        }
    }
}

GCD를 통해 LCM을 구할 수 있다.

외우자.