[JAVA] 프로그래머스 알고리즘 문제풀이 - Level 2 (15~16번 문제풀이) / Level 0 (224/224) / Level 1 (77/77)

15. N개의 최소공배수

문제

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for(int i=1; i<arr.length; i++){
            answer = getLCM(arr[i], answer);
        }
        
        return answer;
    }
    
    // 최대공약수
    public int getGCD(int a,int b){
        while(b != 0){
            int temp = a % b;
            a = b;
            b = temp;
        }
        
        return a;
    }
    
    // 최소공배수
    public int getLCM(int a, int b){
        return a*b / getGCD(a, b);
    }
}

<작성한 코드>

먼저 최대공약수, 최소공배수를 구하는 메서드를 만들어줬다. 최대공약수는 유클리드 호제법을 이용해서 구해줬고, 최소공배수는 두 수의 곱/최대공약수를 해주면 나오기 때문에 a*b / getGCD(a, b)를 해줬다. 이렇게 한 뒤 answer의 초기값을 arr의 첫 번째 원소로 지정해 줬고 for문을 사용해서 두 번째 원소부터 모든 원소를 반복해 가며 최소공배수를 구해줬다. ㄱ ㅡ뒤 answer을 반환해 줬다.

 

 

 

 

 

16. 멀리 뛰기

문제

class Solution {
    public long solution(int n) {
        long answer = 0;
        long[] arr = new long[n+2];
        
        arr[1] = 1;
        arr[2] = 2;
        
        for(int i=3; i<=n; i++){
            arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
        }
        
        answer = arr[n];
        
        return answer;
    }
}

<작성한 코드>

피보나치 수를 이용하여 문제를 해결했다. arr [n] = arr [n-1] + arr [n-2] 이런 식으로 이전 두 개의 값을 더하면 현재의 값이 나온다. 따라서 arr[1], arr[2]를 계단을 오르는 경우의수인 1, 2 를 대입해줬고 for문을 사용해서 i는 3부터 n까지 반복하면서 arr[i]안에 이전 두개의 값을 더한 값을 1234567로 나누고 그 나머지를 대입해 줬다. 그 뒤 answer에 arr [n]의 값을 넣어주고 answer을 반환하였다.