[백준, Java] 3142번, 즐거운 삶을 위한 노력(정수론)

문제 링크

3142번: 즐거운 삶을 위한 노력

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. N개의 숫자가 주어지며, 수가 주어질 때마다 곱을 진행합니다.

2. 곱을 진행할 때마다 해당 과정 결과가 완전제곱수인 경우에 따라 결과를 출력합니다.

3. 완전 제곱수이면 "DA",  아니면 "NE"을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N개의 곱을 진행하며 완전제곱수인지 확인합니다.

 

3. 각 과정의 대한 결과를 출력합니다.

 

 

완전 제곱수

 

완전 제곱수?

 

1, 4, 9, 16, 25 ...

 

정수의 제곱이 되는 값을 완전 제곱수라고 합니다.

 

곱을 진행할 때 완전 제곱수인지 판별하는 방법!

 

 

기존의 값들을 그대로 곱한다면, 해당 값은 long범위를 벗어날 것입니다.

 

그렇다면 BigInteger를 사용해야하는데,  BigInteger는 시간복잡도가 매우 나쁘기 때문에 시간초과가 발생합니다.

 

 

그래서, 저는 소인수 분해를 이용하였습니다.

 

소인수 분해를 했을 때 각 소수의 계수가 짝수이면 정수의 제곱근을 만들 수 있습니다.

 

예를 들어

 

64 = 2 × 2 × 2 × 2 × 2 × 2 = 2의 6승

 

2의 계수가 짝수이기 때문에 제곱근을 구한다면 2³인 것을 구할 수 있습니다.

 

※ 제곱근은 계수에 대해서 ÷ 2을 한 값이기 때문입니다.

 

 

결과적으로, 곱하는 값에 대해서 소인수 분해를 진행한 이후 계수가 홀수인 값이 존재하면 "NA", 모두 짝수이면 "DA"을 결과로 출력하면 됩니다.

 

예제입력 2.

1. 입력된 정보를 저장합니다.

 

N : 7

 

 

 

2

3

6

15

35

21

64

 

2. 나눠떨어지는 개수를 탐색합니다.

 

현재 곱하는 값 : 2

 

소인수 분해 : 2¹

 

홀수인 소수(2)가 존재하기 때문에 "NE"

 

 

현재 곱하는 값 : 3

 

소인수 분해 : 2¹ × 3¹

 

홀수인 소수(2, 3)가 존재하기 때문에 "NE"

 

 

현재 곱하는 값 : 6

 

소인수 분해 : 2² × 3²

 

모든 소수의 계수가 짝수이기 때문에 "DA"

 

 

현재 곱하는 값 : 15

 

소인수 분해 : 2² × 3³ × 5¹

 

홀수인 소수(3, 5)가 존재하기 때문에 "NE"

 

 

현재 곱하는 값 : 35

 

소인수 분해 : 2² × 3³ × 5² × 7¹

 

홀수인 소수(3, 7)가 존재하기 때문에 "NE"

 

 

현재 곱하는 값 : 21

 

소인수 분해 : 2² × 3⁴ × 5² × 7²

 

모든 소수의 계수가 짝수이기 때문에 "DA"

 

 

현재 곱하는 값 : 64

 

소인수 분해 : 2ⁿ(n=8) × 3⁴ × 5² × 7²

 

모든 소수의 계수가 짝수이기 때문에 "DA"

 

 

3. 각 과정의 대한 결과를 출력합니다.

 

과정에서 얻은 결과를 출력합니다.

 

NE

 

NE

 

DA

 

NE

 

NE

 

DA

 

DA

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 1 ~ 1000000까지 에라토스테네스 체로 소수 판정을 하였습니다.
• N개의 수를 소인수 분해하여 곱한 뒤, 소수 계수 비교를 진행합니다.
• 소수 계수의 홀수인 값이 존재하면 "NE",  없으면 "DA"을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw;bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        //최대 입력되는 숫자
        final int MAX_VALUE = 1000000;
        //소수 판정 배열
        boolean[] isPrime = new boolean[MAX_VALUE + 1];
        //계수 홀수 확인 배열
        boolean[] primeFactor = new boolean[MAX_VALUE + 1];
        //소수 리스트
        List<Integer> primes = new ArrayList<>();
        //에라토스테네스 체, 소수 판정 진행
        for(int i=2; i<=Math.sqrt(MAX_VALUE); i++){
            if(!isPrime[i]){
                for(int j=2; i*j<=MAX_VALUE; j++){
                    isPrime[i*j] = true;
                }
            }
        }
        //소수 정보 저장
        for(int i=2;i<=MAX_VALUE;i++){
            if(!isPrime[i]){
                primes.add(i);
            }
        }
        int cnt = 0;
        //N개의 과정 탐색 진행
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            //소인수 분해 진행 및 계수 비교
            for(int prime : primes){
                //더 이상 소인수 분해 불가능한 값 1일 때
                if(num == 1){
                    break;
                }
                //현재 값이 소수일 때
                if(!isPrime[num]){
                    //계수 홀수, 짝수 설정
                    cnt += primeFactor[num] ? -1 : 1;
                    primeFactor[num] = !primeFactor[num];
                    break;
                }
                //소인수 분해 진행
                while(num % prime == 0){
                    num /= prime;
                    //현재 소수 계수 홀수, 짝수 설정
                    cnt += primeFactor[prime] ? -1 : 1;
                    primeFactor[prime] = !primeFactor[prime];
                }
            }
            //홀수인 계수가 없을 때
            if(cnt == 0){
                bw.write("DA\n");
            }else{	//홀수인 계수가 1개라도 있을 때
                bw.write("NE\n");
            }
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}