[BOJ] 2904 수학은 너무 쉬워 - Java

[원본 링크]

https://adorable-aspen-d23.notion.site/BOJ-2904-bd671fa7811442e38f73bf58f483a75f

[BOJ] 2904

 

2904번: 수학은 너무 쉬워

2904번: 수학은 너무 쉬워

[풀이]

• 처음에는 수가 1,000,000 (백만)이라 소인수분해가 아니라 다른 방법으로 풀어야 할 것이라고 생각했지만 마땅한 방법이 떠오르지 않았다.
• 근데 백만정도면 소인수분해 해도 되는 수인가보다(민망)
• 모든 자연수는 소수의 곱으로 이루어져 있다.

1. 입력받는 수 중 가장 큰 수보다 작은 소수들을 에라토스테네스의 체를 이용하여 구한다. ArrayList<Integer> *allPrimes*

2-1. 각 수들을 소인수분해하여, 각 수에 어떤 소수가 몇 번 쓰였는지를 기록한다. ArrayList<HashMap<Integer,Integer>> *numPrimeArrayList*

→ 처음 int[][] numPrime;를 이용하였지만 메모리 초과가 발생하여 HashMap을 이용하여 수를 기록하였다.

2-2. 전체적으로 어떤 소수가 몇 번 쓰였는지도 기록한다. int[] *eachPrimes*;

1. ‘A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.’ 에서 하나에서 나눠졌으면 다른 하나에 곱해지므로 전체로 봤을 때 소수의 갯수는 변하지 않는 것을 알 수 있다.→ 최고 점수에서 쓰이는 각 소수의 갯수 = 각 소수 총 갯수 / 입력받는 수 갯수
2. → ArrayList<info> *MaxGcd 에 저장한다.*
3. → 따라서 최고 점수는 각 소수들을 공평하게 나누어 가졌을 때 임을 알 수 있다.
4. 각 숫자 돌아가면서 MaxGcd에 존재하는 소수를 iterate하는데,(hashMap을 사용하여 각 숫자가 어떤 소수를 가지고 있는 경우와 없는 경우는 따로 갱신하였다.)
5. 각 숫자가 가진 어떤 소수 갯수 < MaxGcd가 가진 어떤 소수 갯수 ⇒ 부족한 것이므로 이동해야 한다. answer를 갱신한다.

 

[코드]

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Boj2904_수학은너무쉬워 {
    static int MAX;
    static int N;
    static PriorityQueue<Integer> nums = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Integer.compare(o2,o1);
        }
    });
    static boolean[] isPrime;
    static ArrayList<Integer> allPrimes = new ArrayList<>();
    static int[] eachPrimes; //eachPrimes[num] = count
    static ArrayList<HashMap<Integer,Integer>> numPrimeArrayList = new ArrayList<>(); //numPrimeArrayList.get(N).get(1~10000) = count
    static ArrayList<info> MaxGcd = new ArrayList<>();

    static int maxGcd=1;
    static int answerCount = 0;

    public static void main(String[] args) throws Exception{
        //입력부
				System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<N+1;i++){
            nums.add(Integer.parseInt(st.nextToken()));
        }
        MAX = nums.peek();
        eachPrimes = new int[MAX+1];

        //0. 1000000보다 작은 모든 소수들 구하기
        isPrime = new boolean[MAX+1];
        findAllPrimes();

        //1. 각 수들을 소인수분해한다.
        for(int i=1;i<N+1;i++){
            int a = nums.poll(); 
            for(int prime:allPrimes){
                //각 소수들로 나눠지면 기록
                while(a % prime == 0){
                    if(a == 1){
                        break;
                    }
                    a /= prime;
                    eachPrimes[prime]++; //각 소수 count 기록
                    if(hm.containsKey(prime)){ //각 num에 prime count 기록
                        hm.put(prime,hm.get(prime)+1);
                    }
                    else{
                        hm.put(prime,1);
                    }
                }
            }
            numPrimeArrayList.add(hm);
        }

        //2. MaxGcd 구하기
        for(int i=1;i<MAX+1;i++){
            if(eachPrimes[i]!=0){
                MaxGcd.add(new info(i,eachPrimes[i]/N)); //이걸 MaxGcd에 저장
                maxGcd = (int) (maxGcd * Math.pow(i,eachPrimes[i]/N));
            }
        }

        //3. 각 numPrime 돌면서 , prime iterate
        for(int i=0; i<MaxGcd.size();i++){
            //각 MaxGcd에 대하여 -> numPrime[i] 비교
            for(int j=1;j<N+1;j++){
                HashMap<Integer,Integer> arrayIt = numPrimeArrayList.get(j-1);
                if(arrayIt.containsKey(MaxGcd.get(i).data)){
                    if(arrayIt.get(MaxGcd.get(i).data) < MaxGcd.get(i).count){
                        answerCount += MaxGcd.get(i).count - arrayIt.get(MaxGcd.get(i).data);
                    }
                }
                else{ //안들어있으면 그대로 다 넣기
                    answerCount += MaxGcd.get(i).count;
                }
            }
        }
        System.out.println(maxGcd+ " " +answerCount);
    }

		//에라토스네테스의 체
    private static void findAllPrimes() {
        for(int i=2;i<=MAX;i++){
            if(isPrime[i]){
                continue;
            }
            allPrimes.add(i);
            for(int j=i+i;j<=MAX;j+=i){
                isPrime[j] = true;
            }
        }
    }
	static class info{
      int data;
      int count;

      public info(int data, int count) {
          this.data = data;
          this.count = count;
      }
  }
}

 

얻어가는 것

• 에라토스테네스의 체

static boolean[] isPrime;
static ArrayList<Integer> allPrimes = new ArrayList<>();

private static void findAllPrimes() {
    for(int i=2;i<=MAX;i++){
        if(isPrime[i]){
            continue;
        }
        allPrimes.add(i);
        for(int j=i+i;j<=MAX;j+=i){
            isPrime[j] = true;
        }
    }
}

• 메모리초과
  • int[][] = new int[100][1000000] 의 경우 128MB에서 메모리 초과가 발생한다.
  • 쳇 빡세다
• 소인수분해하기

//num 소인수분해하기
HashMap<Integer,Integer> factorization(int num){
	HashMap<Integer,Integer> hm = new HashMap<>(); //어떤 소수가 몇 번 쓰였는지를 기록

	**for(int prime : allPrimes)**{ //1. 모든 소수들을 돌아가며 소인수분해 한다. (2부터 모든 수 해도 됨)
		**while(num % prime == 0){** //2. 나눴을 때 나머지가 0이면 계속 그 prime으로 진행
			if(num==1){ //1이면 그만해도 됨
				break;
			}
			**num = num / prime;**

			if(hm.containsKey(prime)){ //있으면 +1
				hm.put(prime,hm.get(prime)+1);
			}
			else{ //없으면 생성
				hm.put(prime,1);
			}
		}
	}

return hm;
}

느낀점

"220204"

소요 시간 : 4h

• 메모리 초과 빡친당
• 너무 복잡하다 , 복잡한 구현 할 때 뇌가 멈추는건 어케 해야하지
• 변수명을 잘 지어서 알아보기 쉽게 하자..