📙[Algo] 24.01.14 알고리즘

알고리즘 문제) BOJ 6219. 소수의 자격

6219번: 소수의 자격

문제 요약

• A..B에서 숫자 D를 포함하는 소수의 개수
  • 자릿값에 D가 몇 개 등장????

시간 제한

• 2초

입력

• A B D
  • 1 ≤ A ≤ B ≤ 4백만
  • B ≤ A + 2백만

출력

• 범위 내에서 숫자 D를 포함하는 소수의 개수?

접근법

• 그냥 1부터,,,4백만까지 에라토스테네스체 사용해서 소수 판별 미리 기록 하고
  • 범위 내에서 자릿값 체크하면서 D가 등장하는 횟수 카운트 하기…!!!!
  • D가 등장하는 소수 개수 카운트 하는거야,,, 문제 잘 읽기,,,

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        boolean[] isPrime = new boolean[4000010];
        Arrays.fill(isPrime, true);
        isPrime[1] = false;
        for (int i = 2; i <= 4000000; i++) {
            if(!isPrime[i]) continue;

            if ((long)i * i <= 4000000) {
                for (int j = i * i; j <= 4000000; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        int cnt = 0, tmp;
        boolean check;
        for (int i = A; i <= B ; i++) {
            if (isPrime[i]) {
                tmp = i;
                check = false;
                while (tmp > 0) {
                    if(tmp % 10 == D){
                        check = true;
                        break;
                    }
                    tmp /= 10;
                }
                if(check) cnt++;
            }
        }

        // 자릿값을 계산하는게 아니라 ㅠㅠㅠㅠ
        // 저 숫자를 포함하는 소수 개수를 구하는거얌,,, 문제 잘읽자...ㅠㅠㅠ

        System.out.println(cnt);
    }
}

 

알고리즘 문제) BOJ 15996. 팩토리얼 나누기  

15996번: 팩토리얼 나누기

문제 요약

• N!를 소수 A의 k승으로 나누었을 때, 나머지가 0이 되는 최대 음이 아닌 정수 k는?

시간 제한

• 1초

입력

• N A (0≤N<2^31, 2≤A≤11, A는 소수)

출력

• 최대 음이 아닌 정수 k 출력

접근법

• N을 A, A^2, A^3…으로 각각 정수 나눗셈하여 몫을 구하고 합한다.
  • 나누는 값이 N보다 작거나 같을 때 까지
  • 왜 int랑 long이랑 같이 연산하면 /by zero 에러가 뜨는거지..? 자동 형변환 되는 게 아니었니..
    • 일단 long타입으로 통일 시킴

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());

        long N = Long.parseLong(st.nextToken());
        long A = Long.parseLong(st.nextToken());

        int cnt = 0;
        long tmp = A;
        while(tmp <= N){
            cnt += N/tmp;
            tmp *= A;
        }

        System.out.println(cnt);
    }
}

 

알고리즘 문제) BOJ 2725. 보이는 점의 개수  

2725번: 보이는 점의 개수

문제 요약

• (0,0)에서 보이는 (x,y)개수 구하기 (x,y≥0, 정수)
  • (0,0)에서 (x,y)를 연결하는 직선이 다른 점을 통과하면 X
• N이 주여졌을 때, 원점에서 보이는 (x,y)좌표 개수 출력
  • (0≤x,y≤N)

시간 제한

• 1초

입력

• 테스트 케이스 C ( 1~1000)
• 자연수 N (1~1000)

출력

• 케이스별로 (0,0)에서 보이는 (x,y)개수 출력

접근법

• 좌표값 x,y가 서로 서로인 거 찾기
  • 서로소는 공약수가 1뿐인거
• 테스트케이스가 최대 1000개 가능하고, 좌표범위도 최대 1000000까지 가능하기 때문에 하나하나 탐색하면서 서로소인지 체크하면 시초뜸
  • 대칭을 생각했을 때 전체 좌표중 절반만 봐도 됨(나중에 카운트한 값*2)
  • 1~x중 x의 약수의 개수 빼기
  • n = 0 ⇒ 0
  • n =1 ⇒ 3
    • 이후부터는 3을 기본적으로 더할 것
  • n>1 ⇒ 2부터 1~x중 x에서 x의 약수의 개수 빼기+1(1은 포함)
    • 1~x중 x의 약수의 배수인 애들도 빼야함 ;;;
    • 그냥 GCD 알고리즘 사용해서 최대공약수가 1인것만 체크
  • 그다음 곱하기 2해서 출력
• 시간초과 어켈해결하지
  • 메모이제이션..?
    • 미리 2부터 1000까지(최대) 서로소인 좌표 갯수를 누적합으로 구하기
  • 그다음 케이스별로 배열에 접근해서 값 출력

코드

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));
        StringBuilder sb = new StringBuilder();

        // 미리 서로 좌표 개수 담기
        int[] memo = new int[1001];
        int cnt;
        for (int i = 2; i <= 1000; i++) {
            cnt = 0;
            for (int j = 1; j <= i ; j++) {
                int tmp = 0, a = i, b = j;
                while(b != 0){
                    tmp = a % b;
                    a = b;
                    b = tmp;
                }
                if(a == 1) cnt++;
            }
            memo[i] = memo[i-1]+cnt*2;
        }

        int C = Integer.parseInt(br.readLine());
        int n, sum;
        while (C-- > 0) {
            n = Integer.parseInt(br.readLine());
            sum = 0;
            if (n == 0) {
                sb.append(0+"\n");
            } else if (n == 1) {
                sb.append(3 + "\n");
            } else {
                sb.append(memo[n]+3 + "\n");
            }
        }
        System.out.println(sb);

    }
}

 

알고리즘 문제) BOJ1990. 소수인팰린드롬  

1990번: 소수인팰린드롬

문제 요약

• 두 정수 a,b가 주어질 때
• a이상 b이하인 소수들 중 팰린들롬 구하기
  • 팰린드롬 : 앞으로 읽거나 뒤로 읽거나 같은 수

시간 제한

• 1초

입력

• a b
  • 5 ≤ a < b ≤ 1억

출력

• 차례로 증가하는 순서대로 소수인 팰린드롬 출력
• 마지막에는 -1출력

접근법

• 먼저 팰린드롬 체크 → 소수판정 (반대로 하니까 시초뜸)
• 팰린드롬 체크할 때 거의 노가다로 했는데,, 다른 방법 없을까?

코드

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

public class Main {

    static boolean isPrime(int num){
        int tmp = num;
        int cnt = 0;
        for (int j = 2; j * j <= num; j++) {
            while (tmp % j == 0) {
                tmp /= j;
                cnt++;
            }
        }
        if(cnt==0) return true;
        else return false;
    }

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

        // 1. 팰린드롬인지 체크 -> 2. 소수인지 체크

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        boolean check;
        for (int i = a; i <= b; i++) {

            // 팰린드롬
            check = false;
            // 팰린드롬 체크
            if (i < 10) {
                check = true;
            } else if (10 <= i && i <= 99) {
                if (i / 10 == i % 10) {
                    check = true;
                }
            } else if (100 <= i && i <= 999) {
                if (i / 100 == i % 10) {
                    check = true;
                }
            } else if (1000 <= i && i <= 9999) {
                if (i / 1000 == i % 10
                        && i / 100 % 10 == i % 100 / 10) {
                    check = true;
                }
            } else if (10000 <= i && i <= 99999) {
                if (i / 10000 == i % 10
                        && i / 1000 % 10 == i % 100 / 10) {
                    check = true;
                }
            } else if (100000 <= i && i <= 999999) {
                if (i / 100000 == i % 10
                        && i / 10000 % 10 == i % 100 / 10
                        && i / 1000 % 10 == i % 1000 / 100) {
                    check = true;
                }
            } else if (1000000 <= i && i <= 9999999) {
                if (i / 1000000 == i % 10
                        && i / 100000 % 10 == i % 100 / 10
                        && i / 10000 % 10 == i % 1000 / 100) {
                    check = true;
                }
            } else {
                if (i / 10000000 == i % 10
                        && i / 1000000 % 10 == i % 100 / 10
                        && i / 100000 % 10 == i % 1000 / 100
                        && i / 10000 % 10 == i % 10000 / 1000) {
                    check = true;
                }
            }

            // 소수 판정
            if(check && isPrime(i)) sb.append(i + "\n");

        }

        sb.append(-1);
        System.out.println(sb);


    }
}

 

알고리즘 문제) BOJ23888. 등차수열과 쿼리  

23888번: 등차수열과 쿼리

문제 요약

• 초항 a, 공차 d
• Ai : 수열의 i번째 원소
• 다음 쿼리를 수행하시오
  • 1 l r = Al + … + Ar
  • 2 l r = Al부터 Ar까지의 최대 공약수 출력

시간 제한

• 2초

입력

• 초항 a, 공차 d
  • 1 ≤ a ≤ 100만
  • 0 ≤ d ≤ 100만
• 쿼리 개수 q
  • 1 ≤ q ≤ 100만
• q개 줄에 각 쿼리가 주어짐
  • 1 ≤ l ≤ r ≤ 100만

출력

• 각각의 쿼리 정답 출력

접근법

• 쿼리가 최대 100만개 주어질 수 있으므로 각 쿼리당 200개 연산을 넘기면 안됨
• 1번 유형 ⇒ O(1)
  • Al 부터 Ar 까지 등차수열 합계 출력
    • O(1) 시간 ⇒ 공식 사용
      • 4 8 12 16 20 = 60
      • an = a1 + (n-1)*d;
      • a3 ~ a5까지 합계 : 48 (l: 3, r:5)
        • n/2*(al+ar) + n%2*(al+(n/2)*d)
        • n = r-l+1;
• 2번 유형
  • Al … Ar의 최대 공약수 출력
  • l이랑 r이랑 같을 때, 공차가 0일 때 체크
  • 첫항이 공차로 나누어 떨어질 때도 체크
  • 그 외에는 (첫항 - 공차)와 공차의 최대 공약수 구해야함
  ⇒ 일일이 노가다로 돌려가면 규칙성 찾아서 내린 결론 ^^
• 가장 중요한건 타입 체크
  • 나는 10의 6승이길래 int형으로 받으면 되는 줄 알았는데, 계산된 값이 int 범위를 벗어난 경우가 있었음
  • 빌드 타임에서 에러가 안떠서 long타입으로 잘 반환될 줄 알았는데,, int형이 섞여서 계산되면,,??? 제대로 값이 안뜨는 거 같다.;;;;

코드

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

public class Main {

    static long func1(long a1, long d, long l, long r){
        long n = r - l + 1;
        long al = a1 + (l - 1) * d;

        return n * (2 * al + (n - 1) * d) / 2;
    }

    static long func2(long a1, long d, long l, long r){
        long answer = 0;

        if(l == r || d == 0){
            answer = a1 + (l - 1) * d;
        } else if (a1 % d == 0) {
            answer = d;
        }else {
            // (첫항 - 공차)와 공차의 최대 공약수 구해야함
            long tmp = 0;
            long a = Math.abs(a1 - d), b = d;
            while (b != 0) {
                tmp = a % b;
                a = b;
                b = tmp;
            }

            answer = a;
        }

        return answer;
    }

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

        st = new StringTokenizer(br.readLine());
        long a1 = Long.parseLong(st.nextToken());
        long d = Long.parseLong(st.nextToken());

        int q = Integer.parseInt(br.readLine());
        int type;
        long l, r;
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = Integer.parseInt(st.nextToken());
            l = Long.parseLong(st.nextToken());
            r = Long.parseLong(st.nextToken());

            if(type==1){
                sb.append(func1(a1, d, l, r) + "\n");
            }else{
                // 무조건 공차의 약수중 왼쪽에 있는 수
                // 만약 20이면 (1, 2, 4)는 해당 수열의 모든 원소의 공약수가 됨
                // 즉 왼쪽에 올 수 있는 수중 최댓값이 모든 수의 최대공약수가 되는것 히히
                sb.append(func2(a1, d, l, r) + "\n");
            }
        }

        System.out.println(sb);

    }
}

 

알고리즘 문제) BOJ1407. 2로 몇 번 나누어질까  

1407번: 2로 몇 번 나누어질까

문제 요약

• 함수 f(X)
  • 자연수 X가 주어질 때, X의 모든 약수 중 2의 거듭제곱 꼴의 가장 큰 약수 반환(2로 몇 번 나눌 수 있는지??)
• 두 자연수 A, B(A≤B)가 주어질 때, A이상 B이하의 자연수 중, f(x)의 합을 구하기

시간 제한

• 2초

입력

• A B (1≤A≤B≤10^15)

출력

• A~B의 f(x)합

접근법

• 타입 → long
• A가 B가 10^15가 주어지면 무조건 시간초과가 뜨므로 규칙성을 찾아야함
• A부터 B까지 모든 합계를 구하면 안된다!!!!
  • 홀수는 무조건 1이 나옴
  • 2 : 2 6 10 14 18 22 26 30 ... (4)
  • 4 : 4 12 20 28 36 ... (8)
  • 8 : 8 24 .. (16)
  • sum = 1*(n/2+1(홀수로 끝날때) or n/2(짝수로끝날 때)) + 2*((n-2)/4+1) + 4*((n-4)/8 + 1) + ...

코드

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

public class Main {

    static long func(long num){
        long sum = 0;

        // 먼저 홀수개만큼 더하기
        if (num % 2 == 0) {
            sum += num / 2;
        } else {
            sum += num / 2 + 1;
        }

        long i = 2;
        while ((num / i) != 0) {
            sum += i * ((num - i) / (i * 2) + 1);
            i *= 2;
        }

        return sum;
    }

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

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
      
        System.out.println(func(B) - func(A - 1));
    }
}

 

알고리즘 문제) BOJ2436. 공약수  

2436번: 공약수

문제 요약

• 자연수가 주어졌을 때, 두 수를 최대공약수와 최소 공배수로하는 두 개의 자연수 구하기

시간 제한

• 1초

입력

• 두 자연수 (2~1억)

출력

• 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 오름차순으로 출력
  • 여러개 있는 경우 합이 최소가 되는 두 수 출력

접근법

GCD * LCM = A * B

• 위에 조건을 만족하는 두 수 찾기
  • 먼저 GCD * LCM 의 약수들을 구하고
  • 최대공약수, 최소공배수 같은 애들만 필터링
  • 그 중 합이 최소가 되는 친구들로 갱신
  • 출력할 때는 오름차순 정렬 후 출력
• 숫자 범위 주의(곱하면 long 타입 됨)

코드

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

public class Main {


    static long getLCM(long a, long b, long gcd){
        return  a/gcd*b;
    }

    static long getGCD(long a, long b){
        long tmp = 0;
        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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long gcd = Integer.parseInt(st.nextToken());
        long lcm = Integer.parseInt(st.nextToken());

        // gcd * lcm = a * b;
        // => gcd * lcm의 약수 먼저 구하기
        // 그다음 LCM, GCD 구하고 일치하면 출력

        long sum  = Long.MAX_VALUE;
        long n = gcd * lcm;
        long[] answer = new long[2];
        for (long i = 1; i * i <= n; i++) {
            if ((gcd * lcm) % i == 0) {
                if(getGCD(i, n / i) == gcd && getLCM(i, n / i, gcd) == lcm){
                    if (sum > i + n / i) {
                        sum = i + n / i;
                        answer[0] = i;
                        answer[1] = n / i;
                    }
                }
            }
        }

        Arrays.sort(answer);
        System.out.println(answer[0] + " " + answer[1]);

    }
}