개발 블로그

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

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

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

출력

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);



        }
    }
}

 

 

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

접근 방법

이 문제는 규칙을 잘 찾아야하는 문제이다. 문제에서 주어진 조건을 봐보면 키를 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);
    }

}

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

문제

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;
}

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

문제

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;}

}

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

문제

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

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가 소수니까 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;
}

문제 링크 : 

www.acmicpc.net/problem/17427

문제

두 자연수 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;
}

문제 링크 : 

www.acmicpc.net/problem/1037

문제

양수 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;
}