📙[Algo] 24.01.17 알고리즘

알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기

14476번: 최대공약수 하나 빼기

문제 요약

• N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1의 최대공약수가 가장 커지는 것을 찾는 프로그램 찾기
  • 이때 최대공약수는 K의 약수면 X

시간 제한

• 2

입력

• 정수의 개수 N(4≤N≤1,000,000)
• N개의 수가 주어짐(20억 이하 자연수)

출력

• 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수와 수 출력
• 정답이 없다면 -1 출력

접근법

8 12 24 36 48

• 8 = 1 2 4 8

8 12 20 32 36

• 숫자 K 하나하나 빼가면서 서로 간격들을 비교하고 그 중 최솟값이 K의 약수가 되는지 체크(즉 K를 나눴을 때 나머지가 0인지 체크)
  • 시간복잡도
    • 최악의 상황 : N이 1백만
    • 1백만 * 1백만 ⇒ 시간 초과
    ⇒ 따라서 K 뺄 때마다 일일이 간격 계산하지 않아야 함
• 미리 최대공약수를 구해야하는데,,.
  • diff 배열에서 왼쪽부터 하나씩 그리고 오른쪽부터 하나씩 이동하면서 GCD를 구해준기
    • diff : 4 7 6 2 12
    • LtoR :
      • 4 7 6 2 12
      • 4 7 6 2 12
      • 4 7 6 2 12
    • RtoL : 4 7 6 2 12
  • 만약 K를 제거했다면 제거한 K 기준 좌우 gcd값 끼리 우선 gcd구하고, 그 다음 제거한 K값으로 바뀐 diff 값이랑 gcd 구하기
    • 제거된 k의 idx 기준 LtoR은 idx-2값, RtoL은, idx+1값
      • 이때 LtoR은 idx-2 ≥ 0 인지 체크, RtoL도 idx+1 ≤ diff.length 인지 체크
    • 제거한 K값으로 바뀐 diff 값은
      • idx가 0, nums.length-1일 경우는 비교할 필요 없음
      • 나머지는 diff[idx-1]+diff[idx]
  • 그리고 k % gcd == 0 인지 체크 (아닐 경우면 gcd 최댓값 갱신)

코드

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

public class Main {

    static long getGcd(long a, long b) {
        // a > b 일 것
        long tmp;
        while (b != 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

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

        int N = Integer.parseInt(br.readLine());

        long[] nums = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Long.parseLong(st.nextToken());
        }

//        Arrays.sort(nums);

        long[] diff = new long[N-1];
        for (int i = 0; i < N-1; i++) {
            diff[i] = Math.abs(nums[i + 1] - nums[i]);
        }

        long[] LtoR = new long[N-1];
        long[] RtoL = new long[N-1];

        long gcd = diff[0];
        LtoR[0] = gcd;
        for (int i = 0; i < N - 1; i++) {
            gcd = getGcd(Math.max(gcd, diff[i]), Math.min(gcd, diff[i]));
            LtoR[i] = gcd;
        }

        gcd = diff[N-2];
        RtoL[N-2] = gcd;
        for (int i = N-2; i >= 0; i--) {
            gcd = getGcd(Math.max(gcd, diff[i]), Math.min(gcd, diff[i]));
            RtoL[i] = gcd;
        }

        long ansGcd = -1, ansK = 0, tmpGcd, newDiff;
        for (int k = 0; k < N; k++) {
            if (k == 0) {
                tmpGcd = RtoL[k + 1];
            } else if (k == N - 1) {
                tmpGcd = LtoR[k - 2];
            } else {
                newDiff = diff[k - 1] + diff[k];
                if (k - 2 < 0) {
                    tmpGcd = getGcd(Math.max(newDiff, RtoL[k + 1]), Math.min(newDiff, RtoL[k + 1]));
                } else if (N - 2 < k + 1) {
                    tmpGcd = getGcd(Math.max(newDiff, LtoR[k - 2]), Math.min(newDiff, LtoR[k - 2]));
                } else {
                    tmpGcd = getGcd(Math.max(LtoR[k - 2], RtoL[k + 1]), Math.min(LtoR[k - 2], RtoL[k + 1]));
                    tmpGcd = getGcd(Math.max(newDiff, tmpGcd), Math.min(newDiff, tmpGcd));
                }
            }

//            System.out.println(nums[k] + " " + tmpGcd);

            if (nums[k] % tmpGcd != 0) {
                if (ansGcd <= tmpGcd) {
                    ansK = nums[k];
                    ansGcd = tmpGcd;
                }
            }
        }

        if (ansGcd != -1) {
            System.out.println(ansGcd + " " + ansK);
        } else {
            System.out.println(ansGcd);
        }


    }
}

 

알고리즘 문제) BOJ 16970. 정수 좌표의 개수

16970번: 정수 좌표의 개수

문제 요약

• 2차원 좌표 평면 위에서 두 점을 선분으로 이었을 때
• 지나가는 점의 개수가 K개인 선분의 수 구하기
  • 선분의 양 끝점도 포함
  • 가능한 점의 좌표는 ( x, y )
    • 0 ≤ x ≤ N
    • 0 ≤ y ≤ M
    • x, y는 정수

시간 제한

• 2초

입력

• N, M, K
  • 1 ≤ N, M ≤ 50
  • 2 ≤ K ≤50

출력

• 지나가는 점의 개수가 K개인 선분의 수?

접근법

직선이 아니라 선분이다 & 기울기 사용해서 접근

• (0,0) ~ (6,9) → y = 3/2x
  

  x	y
  0	0
  1	3/2
  2	3
  3	9/2
  4	6
  5	15/2
  6	9

• x는 y의 약수
  • 정수 좌표만 나와야하므로 x는 2의 배수 (즉 x2-x1의 배수)여야 한다.
  • 결국 y는 (x2-x1)의 배수*(y2-y1)가 된다.
  • 그러나 여기서 (y2-y1)/(x2-x1)을 약분해야하는데, 결국 최대공약수로 약분하게 됨
    • 즉, 약분된 y2-y1만큼 x2-x1만큼 이동하면 정수 좌표를 만난다,,?
    • 그래서 최대공약수가 선분 위에있는 점의 갯수가 된당

코드

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

public class Main {
    static int N, M, K;
    static int cnt;
    static int[] ans = new int[2];
    static int[][] locs;

    static int getGcd(int a, int b) {
        int tmp;
        while (b != 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

    static void findCase(int depth, int start) {

        if (depth == 2) {

            int x1 = locs[ans[0]][0];
            int x2 = locs[ans[1]][0];
            int y1 = locs[ans[0]][1];
            int y2 = locs[ans[1]][1];

            if (getGcd(Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1))
                    , Math.min(Math.abs(x2 - x1), Math.abs(y2 - y1)))+ 1 == K) {
                cnt++;
            }

            return;
        }

        for (int i = start; i < locs.length; i++) {
            ans[depth] = i;
            findCase(depth+1, i+1);
        }

    }

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        locs = new int[(N+1)*(M+1)][2];
        for (int i = 0, x = 0, y = 0; i < locs.length; i++) {
            locs[i][0] = (x++) % (N + 1);
            locs[i][1] = y;
            if (i % (N + 1) == N) {
                y++;
            }
        }
//        for (int i = 0; i < locs.length; i++) {
//            System.out.println(locs[i][0]+" "+locs[i][1]);
//        }
//        System.out.println(locs.length);

        findCase(0, 0);
        System.out.println(cnt);

    }
}