[BOJ 백준] 수학은 너무 쉬워(2904) C++, Java

 

링크 : https://www.acmicpc.net/problem/2904

2904번: 수학은 너무 쉬워

 

문제 설명 : 

상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.

두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.

상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.

상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.

 

입력 : 

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.

출력 : 

 

 첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다.

 

예제 입력 : 

3
8 24 9

예제 출력 : 

12 3

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

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

// 분수 합 1735 
public class Main {
	
	static final int MAX_NUMBER_SIZE = 1_000_000 + 3;

	static boolean[] isNotPrimenumber = new boolean[MAX_NUMBER_SIZE];	// true 소수 아님  / false 소수임
	static ArrayList<Integer> pnList = new ArrayList<Integer>();		// 소수리스트
		
	static int N, maxScore, cnt;
	
	public static void main(String[] args) throws IOException {
		
		// 0-1. 에라토스테네스의 체
		makePrimenumber();

		// 0-2. 소수리스트 만들기
		makePrimenumberList();
		
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		// ** 준비물
		// 1) 소수 사용횟수 카운트
		int[ ] pnUsedCnt = new int[pnList.size()];
		

		// 2) i번째 숫자를 소인수 분해했을때 각 소수의 개수
		//     2번째 숫자를 인수분해 했을때 2, 3, 7 로 인수 분해 됐다고 가정하면
		//        usingPnCnt.get(1).get(0) = usingPnCnt.get(1).get(1) = usingPnCnt.get(1).get(3) = 1; 
		int[][] usingPnCnt = new int[N][pnList.size()];
		

		int input;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
		{
			input = Integer.parseInt(st.nextToken());
			for (int j = 0; j < pnList.size(); j++)
			{
				//소인수분해
				while ( input% pnList.get(j) == 0  )
				{
					pnUsedCnt[j]++;
					usingPnCnt[i][j]++;
					
					input /= pnList.get(j);
					
					// ** 탈출조건
					if (input == 1) {
						break;
					}
				}
				// 소인수분해 완료
				if (input == 1) {
					break;
				}
			}
		}

		maxScore = 1;
		cnt = 0;
		int tmp;
		for (int i = 0; i < pnList.size(); i++)
		{
			// 최대공약수 일부인지 확인
			tmp = pnUsedCnt[i] / N; 

			for (int j = 0; j < tmp; j++) {
				maxScore *= pnList.get(i);
			}

			for (int j = 0; j < N; j++) {
				if (tmp > usingPnCnt[j][i] ) {
					cnt += ( tmp - usingPnCnt[j][i] );
				}
			}
		}
		
		bw.write(maxScore + " " + cnt);
		
		bw.flush();
		bw.close();
		br.close();
	}

	// 0-1. 에라토스테네스의 체
	private static void makePrimenumber() {
		for (int i = 2; i * i < MAX_NUMBER_SIZE; i++)
		{
			if (isNotPrimenumber[i] == false) {
				for (int j = i * i; j < MAX_NUMBER_SIZE; j += i)
				{
					isNotPrimenumber[j] = true;
				}
			}	
		}
	}
	
	// 0-2. 소수리스트 만들기
	private static void makePrimenumberList() {
		pnList.add(2);
		for (int  i = 3; i< MAX_NUMBER_SIZE; i+=2) {
			if (isNotPrimenumber[i] == false) {
				pnList.add(i);
			}
		}
	}


}

 

C++ 코드 : 

// 수학은 너무 쉬워 2904
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

#define MAX (1000000+3)

using namespace std;

bool isNotPrimenumber[MAX];		// true 소수 아님  / false 소수임

void makePrimenumber() {
	// 0-1. 에라토스테네스의 체
	for (int i = 2; i * i < MAX; i++)
	{
		if (isNotPrimenumber[i] == false) {
			for (int j = i * i; j < MAX; j += i)
			{
				isNotPrimenumber[j] = true;
			}
		}
	}
}

int N;
vector<int> pnList;

void makePrimenumberList() {
	pnList.push_back(2);
	for (int i = 3; i < MAX; i+=2) {
		if (isNotPrimenumber[i] == false) {
			pnList.push_back(i);
		}
	}
}

int maxScore, cnt;

int main() {
	// 0. 소수 사전 작업
	makePrimenumber();
	makePrimenumberList();


	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	// 준비물
	// 소수 사용횟수 카운트
	vector<int> pnUsedCnt(pnList.size(), 0);
	//i번째 숫자를 소인수 분해 했을 때 각 소수의 개수
	vector<vector<int>> usingPnCnt(N, vector<int>(pnList.size(), 0));
	
	int input;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &input);
		for (int j = 0; j < pnList.size(); j++)
		{
			//소인수분해
			while ( input% pnList[j] == 0  )
			{
				pnUsedCnt[j]++;
				usingPnCnt[i][j]++;

				input /= pnList[j];
				// ** 탈출조건
				if (input == 1) {
					break;
				}
			}
			// 소인수분해 완료
			if (input == 1) {
				break;
			}
		}
	}

	maxScore = 1;
	cnt = 0;
	int tmp;
	for (int i = 0; i < pnList.size(); i++)
	{
		// 최대공약수 일부인지 확인
		tmp = pnUsedCnt[i] / N; 

		for (int j = 0; j < tmp; j++) {
			maxScore *= pnList[i];
		}

		for (int j = 0; j < N; j++) {
			if (tmp > usingPnCnt[j][i]) {
				cnt += (tmp - usingPnCnt[j][i]);
			}
		}
	}
	printf("%d %d", maxScore, cnt);

	return 0;
}
#endif