프로그래머스LV2_6

멀리 뛰기

접근 과정

1. 피보나치 수와 같은 규칙을 가지고 있는 것을 파악
2. dp를 활용하여 n까지 dp[i] = dp[i - 1] + dp[i - 2] 를 수행
3. dp[n]을 반환하여 해결

시행착오

• dp 방식으로 배열로 규칙을 찾아 해결하였는데 채점에서 한 테스트 케이스에서 런타임 에러가 났다.
  

    class Solution {
        public long solution(int n) {
            long mod = 1234567L;
            long[] dp = new long[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            if(n <= 2) return dp[n];
            for(int i = 3; i <= n; i++){
                dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
            }
            return dp[n];
        }
    }

해결 코드

• 시행착오 방향은 맞았는데 n이 1인 경우 배열 크기가 2인데 dp[2]에 값을 넣으려고 해서 런타임 에러가 나는 것이었다. 따라서 n이 1과 2인 경우를 먼저 반환하면 해결된다.
  

    class Solution {
        public long solution(int n) {
            if(n == 1) return 1;
            else if(n == 2) return 2;
            long mod = 1234567L;
            long[] dp = new long[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <= n; i++){
                dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
            }
            return dp[n];
        }
    }

시간복잡도

N개의 최소공배수

접근 과정

1. answer을 1로 초기화
2. arr을 순회하면서 answer과 arr[i]의 최대공약수를 구해 최소공배수를 구하면 해결

시행착오

• 시행착오 없이 접근 과정대로 구현하여 해결
  

해결 코드

    class Solution {
        public int solution(int[] arr) {
            int answer = 1;
            for(int i = 0; i < arr.length; i++){
                int a = Math.max(arr[i], answer);
                int b = Math.min(arr[i], answer);
                int g = gcd(a, b);
                answer = (a / g) * (b / g) * g;
            }
            return answer;
        }
        
        int gcd(int a, int b){
            while(b != 0){
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    }

시간복잡도