2. 숫자 변환하기
코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr) |
풀이 |
1. 동적 계획법(Dynamic Programming) 아이디어를 활용한다. 2. 정수형 배열 dp를 크기 y+1로 선언한 후, 가능한 가장 큰 값(Integer.MAX_VALUE)으로 채운다. 3-1. 각 인덱스를 '만들 수 있는 값'으로 생각한다. 3-2. 각 인덱스 값을 만들기 위해 필요한 연산 횟수를 저장한다 3-3. 그러니까 """dp[ i ] 의 값은 곧 x가 i로 변환되기 위한 연산 횟수""" 인 것임 3-4. 이 과정은 memoization을 위한 것 4. 배열에 만들 수 있는 값을 인덱스로 삼아 최소 연산 횟수를 저장한다 4-1. for문으로 x부터 시작해 y까지 4-2. 만약 dp[i]값이 Integer.MAX_VALUE면, i를 만들 수 있는 방법이 없는 것이므로 continue 5. dp[y]의 값이 Integer.MAX_VALUE라면 -1을, 아니라면 dp[y]의 값을 반환 |
회고 |
- 나 자바에서 동적계획법 썼다 |
코드 (접은 글) |
더보기
import java.util.*;
class Solution {
public int solution(int x, int y, int n) {
int[] dp = new int[y + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[x] = 0;
for (int i = x; i < y + 1; i++) {
if (dp[i] == Integer.MAX_VALUE)
continue;
if (i * 2 <= y)
dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
if (i * 3 <= y)
dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
if (i + n <= y)
dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
}
if (dp[y] == Integer.MAX_VALUE)
return -1;
return dp[y];
}
}
'코테 > DP' 카테고리의 다른 글
[C/C++] 백준 2775, Dynamic Programming (0) | 2022.12.10 |
---|---|
[C/C++] 백준 1463, Dynamic programming (0) | 2022.12.10 |