백준 9613번 GCD 합

문제

링크 : https://www.acmicpc.net/problem/9613

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

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

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

2중 포문을 이용해서 각각의 정수 쌍 마다 gcd 함수를 호출하여 sum 변수에 그 결과값을 더해주면 모든 쌍의 GCD 합이 구해진다. 마지막에 sum을 출력시키면 테스트 케이스 마다의 GCD 합을 구할 수 있게 하였다.
sum 변수는 long형으로 해주어야 오류가 나지 않는다..

결과

백준 17087번 숨바꼭질 6

문제

링크 : https://www.acmicpc.net/problem/17087

나의 풀이

import java.io.*;
import java.util.*;

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());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

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

        int d = arr[0];
        for(int i = 0; i < n; i++) {
            if(i == 1) {
                d = gcd(arr[i - 1], arr[i]);
            } else if(i > 1) {
                d = gcd(arr[i], d);
            }
        }

        System.out.println(d);
    }

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

x에서 동생이 위치한 지점으로 이동하는 경우에 x가 x + d, x - d로만 이동하려면 동생 위치 지점에서 x를 뺀 값이 d의 배수가 되어야 한다.
그렇기 때문에 모든 각각의 동생들 위치 지점에서 x를 뺀 값들 간의 최대공약수를 구해야 한다.
arr 배열에 시작 위치와 동생들의 위치의 차이들을 저장해주고, 각 원소들을 토너먼트 형식으로 gcd함수를 호출하여 모든 원소들의 최대공약수를 구해주게 구현하였다.

결과

백준 1373번 2진수 8진수

문제

링크 : https://www.acmicpc.net/problem/1373

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        
        if(n % 3 == 1) { // 세자리씩 끊었는데 한 자리만 남았을 경우
            System.out.print(s.charAt(0));
        } else if(n % 3 == 2) { // 세자리씩 끊었는데 두 자리만 남았을 경우 
            System.out.print((s.charAt(0) - '0') * 2 + (s.charAt(1) - '0'));
        }
        
        for(int i = n % 3; i < n; i += 3) {
            System.out.print((s.charAt(i) - '0') * 4 + (s.charAt(i + 1) - '0') * 2 + (s.charAt(i + 2) - '0'));
        }
        
        System.out.println();
    }
}

세자리씩 끊어서 2진수를 8진수로 변경시키게 계산시켜주면 된다.

결과