728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1339

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

 


접근 방법

단순하게 생각을 했다.  GCF + ACDEB를 더하려면 어떻게 해야할까?

아직 각 알파벳에 어떤 수를 대입할지 정하지는 않았지만

(100*G + 10*C + F) + (10000*A + 1000*C + 100*D + 10*E + B)  = 

이런 식으로 계산식을 써볼 수 있을 것이다. 

위 식에서 묶을 수 있는 것들을 묶어주면 (같은 알파벳은 같은 수라고 했으므로)

10000*A + 1010*C + 100*D + 100*G + 10*E + F + B 가 될 것이다. 

이제 각 알파벳 앞에 붙어 있는 수가 큰 순서대로 9, 8, 7, 6,,, 이런 식으로 값을 대입해주면 된다. 

 

import java.util.*;
public class BOJ_1339_단어수학 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] strArr = new String[N];
        int[] alphaArr = new int[26];
        Arrays.fill(alphaArr, 0);

        for(int i = 0; i<N; i++){
          String str = sc.next();
          //System.out.println(str);
          int len = str.length();
          for(int j = 0; j<len; j++){
              char c = str.charAt(j);   // c = 'A', 'B' ...
              alphaArr[c - 'A'] += (int)Math.pow(10, len-1-j);  //'A'면 alphaArr[0]
          }
        }

        Arrays.sort(alphaArr);
        int multipleNum = 9;
        int index = 25;
        int sum = 0;
        while(alphaArr[index]>0){
            sum += alphaArr[index] * multipleNum;
            index--;
            multipleNum--;
        }
        System.out.println(sum);
    }
}

 

 

 

참고  : https://mountain96.tistory.com/21

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1722

 

1722번: 순열의 순서

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N

www.acmicpc.net

 

문제

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

 

 


 

접근 방법

주어진 시간은 2초밖에 되지 않기 때문에 노가다로 하면 시간 초과가 뜰 것이다. 

먼저 소문제 번호 = 1인 경우를 보자.

N = 5 

배열 = {1, 2, 3, 4, 5}

k = 61이라고 해보자. 

61번째 순열을 어떻게 구할 수 있을까?

먼저 61번째의 첫번째 숫자는 무엇일지 생각해보자. 2*4! < 61 < 3*4! 이므로 첫번째 숫자는 3이다.

1 _ _ _ _  => 4! (24) 가지가 있음

2 _ _ _ _ => 4! (24) 가지가 있음

3 _ _ _ _ => 4! (24) 가지가 있음

이런 방식을 활용해보면 처음 61에서 24씩 빼면서 경계를 찾아 나가다가 

61 - 24 = 37

37 - 24 = 13

13 - 24 < 0 가 됨. 24를 세번째 뺀 것이므로 세번째 범위에 답이 있고 처음 숫자는 3이 되는 것이다. 

 

그 다음을 보자. 우선 3은 가장 앞자리로 고정이 되었기 때문에 제외하고 1, 2, 4, 5 가 남았다. 

 

3, 1, _ _ _ => 3! (6) 가지가 있음 (49 ~ 54)

3, 2, _ _ _ => 3! (6) 가지가 있음 (55 ~ 60) 

3, 4, _ _ _ => 3! (6) 가지가 있음 (61 ~ 66)- > 이 중에 61번째 순열이 있음 

3, 5, _ _ _ => 3! (6) 가지가 있음 (67 ~ 73)

 

단순하게 보면 위와 같은데, 처음에 썼던 빼기 규칙을 써보면 

13 - 6 = 7 > 0이고

7 - 6  = 1 > 0이고 

1 - 6 <0 이므로 세번째 범위에 답이 있고 두번째 숫자는 4가 되는 것이다. 

이런 식으로 계속 빼 나가면서 숫자를 지정해나가면 된다. 

 

 

다음 소문제 번호 = 2인 경우를 보자.

위에서 했던 방식을 거꾸로 하면 된다. 

N = 5일 때 61번째 순열인 {3, 4 ,1 ,2, 5} 를 보자. {3, 4, 1, 2, 5}를 보고 어떻게 61번째 순열인지 알 수 있을까?

각 자리의 숫자보다 작은 수로 시작하는 순열의 가지수를 세가면서 더하면 된다. 

1, _ _ _ _ 는 4! (24)가지

2, _ _ _ _ 도 4!(24)가지이다. 

그럼 우선 sum은 24+24 = 48이 된다. 

3은 visit 표시를 해 놓고 다음 차례인 4를 보자. 

 

3, 4, _ _ _ <- 이 순열의 전에는 

3, 1, _ _ _  

3, 2, _ _ _

이 두 순열이 우선이 됐을 것이다. 각각 3! (6) 가지이므로 48 + 6 + 6 = 60이 된다. 

 

3, 4, _ _ _ 정해졌고 남은 수는 1, 2, 5 인데 구하는게 3, 4, 1, 2, 5가 몇번째인지 구하는 것이므로 

sum 인 60에 1을 더하면 된다. 

 

import java.util.*;
public class BOJ_1722_순열의순서 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long[] fac = new long[21];
        fac[0] = 1;
        for(int i = 1; i<=20 ;i++) fac[i] = i*fac[i-1];

        int N = sc.nextInt();
        int num = sc.nextInt();
        long k = 0;
        int[] arr = new int[N+1];
        boolean[] visited = new boolean[N+1];
        Arrays.fill(arr,0);
        Arrays.fill(visited,false);

        Vector<Integer> ansVec = new Vector<Integer>();
        long ans = 1;

        if (num==1){
            k = sc.nextLong();      //Long으로 입력하지 않으면 런타임 에러뜸
            for(int i = 0; i<N; i++){
                for(int j = 1; j<=N; j++){
                    if(visited[j]) continue;    //이미 사용된 숫자는 패스
                    if(k - fac[N-1-i] > 0) {    //0이랑 같으면 1 3 4 2가 오답으로 출력됨 
                        k -= fac[N-1-i];        
                    }
                    else {                         
                        ansVec.add(j);
                        visited[j] = true;
                        break;
                    }
                }
            }
            for(int i = 0; i<ansVec.size(); i++){
                System.out.print(ansVec.elementAt(i) + " ");
            }

        }
        else if (num==2){
            for(int i = 0; i<N; i++){
                arr[i] = sc.nextInt();  
            }
            for(int i = 0; i<N; i++){
                for(int j = 1; j<arr[i]; j++){      //arr[i] 보다는 작은 수가 앞에 나올 수 있으므로 
                    if(visited[j] == false){
                        ans += fac[N-1-i];
                    }

                }
                visited[arr[i]] = true;
            }
            System.out.println(ans);



        }
    }
}

 

 

728x90
728x90

문제 : https://www.acmicpc.net/problem/1669

 

1669번: 멍멍이 쓰다듬기

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍

www.acmicpc.net

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.

그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.

현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.

출력

첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.

 


접근 방법

이 문제는 규칙을 잘 찾아야하는 문제이다. 문제에서 주어진 조건을 봐보면 키를 1cm 차이가 나게 조절을 해야하는데, 이 때 첫째 날과 마지막 날은 무조건 1cm가 되어야 한다. 이 점을 유의깊게 봐보자.

 

우리는 최소의 일수를 구해야 하기 때문에 첫째 날 키 조절 양을 1cm 로 시작을 해서 2, 3, 4,,, 로 키를 키워나가야 하지만

마지막 날의 키 조절 양도 1cm로 끝나야하기 때문에

어느 정도 고점 x에 도달한 뒤에는 x-1, x-2, x-3,,, 1 과 같이 키의 양을 줄여나갸야 하는 것이다. 

 

그렇다면  그 고점을 어떻게 찾아야할까? 

규칙이 보이지 않을 때에는 먼저 나열을 쭉 해보고 그 안에서 규칙을 찾아보는것도 좋은 방법이다. 

 

키 차이 (Y-X) 를 sub이라고 하자. 멍멍이와 원숭이의 키가 같아지기 위한 최소 일수를 찾아보자. 

   * 괄호 안의 수는 각 날에 조절한 키의 양이다.)

sub = 1 일 때 : 1일 (1)

sub = 2일 때 : 2일 (1, 1)

sub = 3일 때 : 3일 (1, 1, 1)

sub = 4일 때 : 3일 (1, 2, 1)

sub = 5일 때 : 4일 (1, 2, 1, 1)

sub = 6일 때 : 4일 (1, 2, 2, 1)

 

sub = 7일 때 : 5 (1, 2, 2, 1, 1)

sub = 8일 때 : 5일 (1, 2, 2, 2, 1)

sub = 9일 때 : 5일 (1, 2, 3, 2, 1)

sub = 10일 때 : 6일 (1, 2, 3, 2, 1, 1)

sub = 11일 때 : 6일 (1, 2, 3, 2, 2, 1)

sub = 12일 때 : 6일 (1, 2, 3, 3, 2, 1)

sub = 13일 때 : 7일 (1, 2, 3, 3, 2, 1, 1)

sub = 14일 때 : 7일 (1, 2, 3, 3, 2, 2, 1)

sub = 15일 때 : 7일 (1, 2, 3, 3, 3, 2, 1)

sub = 16일 때 : 7일 (1, 2, 3, 4, 3, 2, 1)

sub = 17일 때 : 8일 (1, 2, 3, 4, 3, 2, 1, 1)

 

제곱수를 보면 sub = N^2 라고 했을 때 고점이 N 인것을 확인할 수 있고, 필요한 최소 일수는 N^2 - 1 인 것을 확인할 수 있다. 
그렇다면 제곱수가 아닌 수는 어떤 규칙이 있을까?

예를 들어 sub = 13일 때를 보자. 13보다 작은 제곱수인 9(1, 2, 3, 2, 1) 을 제외하면 (1, 2, 3, 3, 2, 1, 1) 중 (3, 1)이 남는데

이는 루트 9보다 작은 수 중 적당히 끼워 넣은 것이다. 

 

즉,

1) 키 차이보다 작은 최대 제곱수 N^2 를 찾고

2) 키 차이에서 최대 제곱수를 뺀 나머지를 구한 다음

3) 나머지가 N이하의 수들로 어떻게 구성되어있는지 찾으면 되는 것이다. (문제에서 최소 일수를 찾는 것이 목표이기 때문에 이때 가장 큰 수인 N부터 검사하도록 한다. )

 

이를 코드로 나타내면 아래와 같다.

 

*주의 ) N과 ans를 long형으로 선언해야한다. (오버플로우 방지 (?) )

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int y = sc.nextInt();
        int sub = y - x;
        
        if(sub == 0){				// 예외처리 : 처음부터 키가 같을 때
            System.out.println(0);
            return;
        }

        long N = 1;				//long 형으로 선언해야한다.
        long ans = 0;

        while(N*N <= sub){ 			//키차이보다 작은 최대 제곱수를 찾는다.
            N++;
        }
        N-=1;					//N++된 상태로 while문을 빠져나오기 때문에 -1 해준다.
        ans = 2*N - 1;				//answer 초기 값 설정 

        sub -= N*N;				//제곱수만큼 빼고 남은 키로 while 문을 돈다.
        while(sub > 0){

            for(long i = N; 1<=i; i--){		//N부터 시작해서
                if(i<=sub){					//i가 sub보다 작으면 
                    ans+=1;
                    sub -= i;				//sub에서 i를 뺀다.
                    break;
                }
                else continue;				
            }
        }
        System.out.println(ans);
    }

}

 

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/10989

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 


 

접근 방법

수 정렬하기 1번과 2번은 vector의 sort()로 쉽게 풀었는데 이번 문제는 N의 범위가 커서 메모리 초과가 난다.

우선순위 큐를 써도 똑같이 메모리 초과가 난다.

그래서 수의 범위가 10,000을 넘지 않는 점을 고려해서 아래와 같이 코드를 작성했다.

 

* 참고

   ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

를 쓰지 않으면 시간초과가 뜬다. 

 

 

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin >> N;
    int arr[10001] = {0,};
    int num =0;
    for(int i = 0; i<N; i++){
        cin >> num;
        arr[num] += 1;
    }
    for(int i = 1; i<=10000; i++){
        for(int j = 0; j<arr[i]; j++){
            cout << i << "\n";
        }
    }
    
    return 0;
}

 

728x90
728x90

문제 링크 : www.acmicpc.net/problem/4375

 

4375번: 1

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

www.acmicpc.net

 

 

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

 

 


접근 방법

숫자를 1, 11, 111, 1111,,,,로 키워가면서 N으로 나눠지는지 따지는 문제이다.

그러나 계속 숫자를 한 자리씩 키워나간다면 long long int 의 범위(-9,223,372,036,854,775,808~9,223,372,036,854,775,807)도 넘어가게 되고 시간초과가 뜬다. 그래서 modular 연산의 활용이 필요하다.

 

x mod N = (x mod N) mod N 임을 이용해보자.

 

예를 들어, 111이 N으로 나눠지지 않아서 1111로 넘어갈 때, 1111을 바로 다음 반복문으로 넘기는 것이 아니라 mod N 연산을 해주고 넘기는 것이다. 그러면 숫자가 계속 커지는 것을 방지할 수 있다.

 

숫자가 매우 커질 때 modular 연산을 이용해서 줄일 수 있다는 것을 기억하자!

//
//  수학_BOJ4375_1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/28.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    
    int N;
    int k = 0;
    while(cin >> N){
        int ans = 1;
        k = 1;
        
        while(1){
            if(ans % N == 0){
                break;
            }
            else{
                k++;
                ans = ans*10 + 1;
                ans %= N;				//mod 연산을 해 준 결과를 다음 반복문으로 넘긴다.
            }
        }
        
        cout << k << "\n";
    }

    return 0;
}

 

 

참고)

 while(cin >> input) 은 입력이 종료될 때 까지 받는다. 

같은 의미로는 아래와 같다.

while(1){

  if(cin.eof() == true) {break;}

}

 

 

 

728x90
728x90

문제링크 : www.acmicpc.net/problem/1929

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

 

 

접근 방식 1 

 

페르마의 정리 이용ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95#%ED%8E%98%EB%A5%B4%EB%A7%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

 

소수판별법 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다. 간단한 방법들[편집] 직접 나

ko.wikipedia.org

gcd(a,p)  = 1 , a<p and p가 소수이면 a^p-1 (mod p) 는 1과 합동이다.

 

그러나 a = 8, p = 9일때, 8^8 = 16777216이어서 이를 9로 나눈 나머지는 1인데, 9는 소수가 아니므로 예외가 발생한다.

 

#include <iostream>
#include <cmath>

using namespace std;

int gcd(int p, int a){
    
    int c;
    while(a!=0){
        c = p%a;
        p = a;
        a = c;
    }
    return p;
}

int main(){
    
    int M, N;
    cin >> M >> N;

    for(int p = M; p<=N; p++){

        for(int a = 2; a<p; a++){

            if(gcd(p,a) == 1){

                int chk =((int)pow(a,p-1)) % p;
                if(chk == 1){
                    cout << "a: " << a << " /p: " << p << endl;
                    break;
                }
            }
        }
    }

    return 0;
}

 

 

 

접근 방법 2

Miller-Rabin Primality Test 를 이용해보자. 

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;


bool Test(int a, int n){
    
    
    int u=0, t=0;
    int k = n-1;
    int tmp = k;
    if(k%2 != 0){   //k홀수 즉 n짝수(합성수 이므로 true return)
        return true;
    }
    
    while(k>=2){
        if(k%2 == 0) {
            t++;
            k /= 2;
        }
    }
    
    u = tmp / pow(2,t);
    
    int x0 = (int)pow(a,u) % n;
    int x=0;
    for(int i = 1; i<=t; i++){
        
        x = (x0*x0) % n;
        
        if(x==1 && x0 !=1 && x0!=n-1){
            return true;
        }
        
        x0 = x;
    }
    if(x!=1) return true;
    
    return false;

}


int main(){
    
    int M, N;
    cin >> M >> N;

   srand((unsigned int)time(NULL));

    for(int n = M; n<=N; n++){
        
        bool chk = true;
        for(int s = 0; s<10; s++){
            
            int a = rand();
            while(a>=n){a = rand();}
            
            if(Test(a,n) == true){
                //합성수
                chk = false;
                break;
            }
            
        }
        
        
        if(chk){ //s번 다 도는 동안 Test()가 모두 false 이면
            //n은 소수
            cout << n << endl;
        }
        
        
        
        
    }
    
    
    
    return 0;
}

시간 초과가 떴다.

 

 

 

 

 

 

 

 

접근 방법 3

 

많은 사람들이 선택한 '에라토스테네스의 체' 방법을 이용했다. 

참고 : ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2

ko.wikipedia.org

 

 

 

2가 소수니까 2의 배수는 소수가 아니다. 그러므로 2의 배수를 쭉 지운다.

3도 소수니까 3의배수는 소수가 아니다. 그러므로 3의 배수를 쭉 지운다.

 

이때 주의할 점은 j의 시작값이다. i*j(j<i)까지는 이미 검사했으므로 j 시작값을 i*2 에서 i*i로 개선할 수 있다.

i=5, j=3일때를 예로 들어보자.

5*3 = 15까지는 이미 i=3일때 검사가 됐다. 그러므로 j시작 값을 10(소수 5의 첫번째 배수)이 아닌 25부터 할 수 있는 것이다. 

더 자세히 따져보기 위해 실제로 2~24의 수 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24  을 봐보자.

 

(i = 2) 2의 배수 4,6,8,10,12,14,16,18,20,22,24 를 checked 한다

(i = 3) 3의 배수 6,9,12,15,18,21,24 를 checked 하는데 사실 이 중 2의 배수들은 i=2일때 이미 checked된 상태이다.

(i = 4) 4의 배수 -> arr[4] = 1이므로 볼 필요도 없이 Pass

(i = 5) 5의 배수 10,15,20 -> 이미 checked된 상태이다.

 

그러므로 j시작값을 i*i 부터 할 수 있는 것이다. 그러면 중복을 제거할 수 있다.

 

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;

int arr[1000001] = {0};
int main(){
    
    
    int M, N;
    cin >> M >> N;

   
    arr[1] = 1; //1은 소수 아님
    
    
    
    for(int i = 2; i*i <= N; i++){
        
        if(arr[i]==0){
            for(int j = i*i; j<=N; j+=i){
                arr[j] = 1;
            }
        }
    }
    
    
    
    for(int i = M; i<=N; i++){
        if(arr[i] == 0 ) cout << i << "\n";
    }
        
    return 0;
}

 

728x90
728x90

문제 링크 : 

www.acmicpc.net/problem/17427

 

17427번: 약수의 합 2

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

 

 

 

 


 

접근 방법 1

직관적으로 풀었더니 제한시간인 0.5초를 넘어서 시간초과가 떴다. f(1)부터 f(N)까지 하나씩 구해서 더하는 방식으로 짜면 안되는 것 같다.

#include <iostream>

using namespace std;


int main(){
    
    int N, ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=i; j++){
            if(i%j == 0) ans +=j;
        }
        
    }
    
    cout << ans << "\n";
    
    return 0;
}


 

 

 

 

 

 

접근방법 2

새로운 접근 방법으로 풀어보았다.

N = 10 일때를 보자.

f(1) = sum(1)

f(2) = sum(1, 2)

f(3) = sum(1, 3)

f(4) = sum(1, 2, 4)

f(5) = sum(1, 5)

f(6) = sum(1, 2, 3, 6)

f(7) = sum(1, 7)

f(8) = sum(1, 2, 4, 8)

f(9) = sum(1, 3, 9)

f(10) = sum(1, 2, 5, 10)

 

이고 약수의 숫자들을 카운팅해보면, 

1 : 10개 (10을 1로 나눈 몫)

2 : 5개(10을 2로 나눈 몫)

3 : 3개(10을 3으로 나눈 몫)

4 : 2개(10을 4로 나눈 몫)

 

.

.

.

.

 

10: 1개(10을 1로 나눈 몫)

 

과 같이 규칙이 있음을 알 수 있다.

 

 

주의)

또한 처음에는 ans 변수를 int 형으로 선언했는데 오류가 났었다. 입출력 예시 자료를 보니 출력값이 82256014였고 이를 이진수로 변환하면 100111001110010000010001110(27비트)로 4바이트를 넘어가서 오류가 나는 거였다. 8바이트인 long long (int생략 가능) 으로 바꿔주니 정답처리가 되었다. 자료형에도 주의하자!!

 

 

#include <iostream>
using namespace std;

int main(){
    
    
    int N;
    long long ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        ans += (N/i)* i;
    }
    
    cout << ans << "\n";
    
    return 0;
}


 

728x90
728x90

문제 링크 : 

www.acmicpc.net/problem/1037

 

1037번: 약수

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되

www.acmicpc.net

 

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

 

 

 

 


접근 방법

N의 진약수 중 크기순으로 나열했을 때, 가장 작은 약수와 큰 약수를 곱하면 N이 나온다는 사실을 이용했다. 

진약수들을 입력받을 때, 크기순으로 입력이 들어오지 않는다는 점을 주의하자!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> vec;

int main(){
    
    int cnt, ans;
    cin >> cnt;
    
    for(int i = 0; i<cnt; i++){
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    
    sort(vec.begin(), vec.end());
    ans = vec[0] * vec[cnt-1];

    cout << ans << "\n";
    
    return 0;
}

 

 

 

728x90

+ Recent posts