1. 점프와 순간 이동
: OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
제한 사항
숫자 N: 1 이상 10억 이하의 자연수
숫자 K: 1 이상의 자연수
[문제 풀이 고민]
앞으로 k칸 점프 시 -> k만큼의 건전지 사용
순간이동 -> 현재까지 온거리 * 2 위치로 기동 가능
(출력) 건전지 사용량의 최솟값을 리턴
- 그리디 알고리즘을 사용해보자
거리 N을 2로 나누어 떨어지는 만큼 순간이동을 하면 최적의 해를 구할 수 있음. 나누어 떨어지지 않을 경우에는 한칸 씩 이동해서 다시 순간이동을 확인한다.
1) 효율성에서 시간초과
- 입력으로 들어올 수 있는 숫자 범위가 문제가 됨
거리 N이 최대 10억이므로 하나하나 하게 되면 시간이 엄청 길게 됨 - 숫자를 1씩 감소시키면서 건전지 사용량을 계산
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.out.println("Hello Java");
while(n > 0){
//2로 나누어떨어질 경우 "순간이동"
if(n % 2 == 0){
n /= 2;
}
//"점프"
else{
n -= 1;
ans += 1;
}
}
return ans;
}
}2) 제출한 코드
- 2로 나누어가면서 건전지 사용량을 계산
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
while(n > 0) {
if(n % 2 == 0) {
n /= 2;
} else {
n -= 1;
ans++;
}
}
return ans;
}
}2. N개의 최소공배수
: 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
[문제 풀이 고민]
n개의 최소공배수로 n개의 수들의 배수중 공통이 되는 수를 구해야함
입력받은 배열 내 2개의 수의 최소공배수를 구한 뒤, 그 최소공배수와 다음 인덱스 값을 비교하여 그 둘의 최소공배수를 구하는 배열 과정을 반복
class Solution {
public int solution(int[] arr) {
int answer = arr[0];
int small = 0;
int big = 0;
for (int i = 1; i < arr.length; i++) {
small = Math.min(answer, arr[i]);
big = Math.max(answer, arr[i]);
answer = (small * big) / gcd(small, big);
}
return answer;
}
public static int gcd(int small, int big) {
int answer = 0;
for (int i = 1; i <= small; i++) {
if (small % i == 0 && big % i == 0) answer = i;
}
return answer;
}
}3. 멀리 뛰기
: 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 사항
n은 1 이상, 2000 이하인 정수입니다.
[문제 풀이 고민]
1 ~ 2칸을 뛸 수 있음
끝에 도달하는 방법의 수를 찾아야함
먼저 DP 배열을 만들어서 n칸에 도달하는 방법의 수를 저장한다. 배열의 크기는 n + 1이 될 것
초기값을 설정하는데 배열의 [0]은 0일 경우라 1, [1]또한 1번만 가면 되므로 1로 설정한다.
2 이상일 경우를 각각 배열에 저장한다.
n-1로 해서 1칸 뛰어서 도달 할 수 있고, n-2 로 뛰어서 도달 할 수 있으므로 (dp[i-1] + dp[i-2])를 설정한다.
class Solution {
public long solution(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
}
return dp[n];
}
}참고 : https://zzang9ha.tistory.com/138
4. 콜라 문제
: 오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
정답은 아무에게도 말하지 마세요.
콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?
단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.
문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.
문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.
콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.
[문제 풀이 고민]
빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산
while로 전체가 a보다 크거나 같을때까지만 반복을 한다.
계속 콜라를 받을 갯수를 answer에 더하고, total를 재 계산하는 식으로 완료함
class Solution {
public int solution(int a, int b, int n) {
int answer = 0;
int total = n;
while(total >= a){
//콜라를 받을 갯수
int temp = (total / a) * b;
answer += temp;
//현재 가지고 있는 갯수
total = (total % a) + temp;
}
return answer;
}
}