반응형
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을 반환하였다.
반응형