🎯문제
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
- n을 더합니다
- 2를 곱합니다.
- 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y
입출력 예
| x | y | n | result |
|---|---|---|---|
| 10 | 40 | 5 | 2 |
| 10 | 40 | 30 | 1 |
| 2 | 5 | 4 | -1 |
입출력 예 설명
입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.
입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.
✏️풀이
코드
class Solution {
public int solution(int x, int y, int n) {
int[] dp = new int[y+1];
for(int i = x; i < y+1; i++) {
// 반복이 진행되면서 나오지 않은 숫자들은 제거
if(i != x && dp[i] == 0) {
dp[i] = -1;
continue;
}
// n을 더했을 때
if(i + n <= y) {
dp[i+n] = dp[i+n] == 0 ? dp[i] + 1 : Math.min(dp[i+n], dp[i] + 1);
}
// 2를 곱했을 때
if(i * 2 <= y) {
dp[i*2] = dp[i*2] == 0 ? dp[i] + 1 : Math.min(dp[i*2], dp[i] + 1);
}
// 3을 곱했을 때
if(i * 3 <= y) {
dp[i*3] = dp[i*3] == 0 ? dp[i] + 1 : Math.min(dp[i*3], dp[i] + 1);
}
}
return dp[y];
}
}설명
dp의 방식을 사용해서 문제를 풀었다.
x부터 시작해 y까지 하나씩 증가하면서 반복을 진행하였는데, 우리가 사용할 연산은 n 더하기, 2 곱하기, 3 곱하기이다. 처음 X에서부터 각각 n 더하기, 2 곱하기, 3 곱하기의 연산을 했을 때 y보다 작거나 같다면 해당 값을 저장한다.
dp의 인덱스는 숫자이고 값은 연산 횟수가 되는 것이다.
이렇게 반복이 한번 진행된 뒤에 첫번째 if문이 매우 중요해진다.
이 if문을 생각하지 못해서 처음 제출할 때 오답이 있었다..
이 첫번째 if문은 반복이 진행되면서 나오지 않은 숫자들을 계산하는 경우를 제거하는 것이다.
예를 들어,
| x | y | n | result |
|---|---|---|---|
| 10 | 40 | 5 | 2 |
일 때 10부터 반복문이 시작된다.
10 + n, 10 x 2, 10 x 3 을 계산한 값인 15, 20, 30의 인덱스에 1의 값들이 들어가게 될 것이다.
그리고 다음 반복을 진행할 때, 11부터 진행이 되는데 이 11은 위의 10에서 어떤 연산을 해도 나오지 않는 값이다. 따라서 계산을 진행할 필요도 없고, 계산을 한다면 오류가 발생할 수 있다.
이러한 방법을 계속 진행하면서 모든 계산이 완료된 뒤 dp[y]의 값에는 -1 혹은 연산의 최솟값이 저장이 되어있을 것이다. 이 값을 반환해준다면 문제를 해결할 수 있다.
💡느낀 점
처음 보자마자 dp 관련한 문제라고 생각이 들었다. 때문에 방식을 떠올리는 것은 어렵지 않았는데, 오히려 생각치도 못한 부분에서 발생한 오류에 대해 고민을 하느라 시간을 좀 썼던 것 같다. 문제를 보면서 오류가 발생할 수 있는 부분에 대해서 생각해보는 연습이 많이 필요하다는 것이 느껴졌다..
링크
