프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
1. 재귀함수로 해결하려 했으나 일부 테스트케이스 시간초과 및 런타임에러 ( 실패 )
2. dp로 해결.
3. int[] dp 사이즈를 y+1 의 크기로 생성 후 dp [ i ] 에 최소 연산 수를 저장
4. dp[x] = 0 으로 초기화하고 반복문 시작
나의풀이 ( 코드 )
class Solution {
public int solution(int x, int y, int n) {
int answer = -1;
int[] dp = new int[y + 1];
for (int i = 0; i < dp.length; i++) {
dp[i] = 1000001;
}
dp[x] = 0;
for (int i = x; i <= y; i++) {
if (dp[x] == 1000001) {
continue;
}
if (i + n <= y) {
dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
}
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 (dp[y] != 1000001) {
answer = dp[y];
}
return answer;
}
}
실패한 풀이 ( 코드 )
class Solution {
static int min = 1000001;
static int sum;
public int solution(int x, int y, int n) {
int answer = -1;
sum = n;
dfs(x, y, 0);
if (min != 1000001) {
answer = min;
}
return answer;
}
static void dfs(int x, int y, int count) {
if (x == y && min > count) {
min = count;
return;
} else if (x > y) {
return;
}
dfs(x * 2, y, count + 1);
dfs(x * 3, y, count + 1);
dfs(x + sum, y, count + 1);
}
}'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스/JAVA 자바] [PCCE 기출문제] 10번 / 데이터 분석 (0) | 2023.11.25 |
|---|---|
| [프로그래머스/JAVA 자바] 2 x n 타일링 (0) | 2023.11.24 |
| [프로그래머스/JAVA 자바] [1차] 프렌즈4블록 (1) | 2023.11.22 |
| [프로그래머스/JAVA 자바] 롤케이크 자르기 (0) | 2023.11.21 |
| [프로그래머스/JAVA 자바] [3차] 파일명 정렬 (1) | 2023.11.20 |