문제: https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
모든 경우의 수를 고려해야 하는 문제이다.
dfs를 푼지 너무 오래되기도 했었고, 볼 때마다 어려운 부분이긴 하다.
내 힘으로 결국 해결하지 못했고, 다른 코드를 참고했다.
참고한 코드는 아래와 같고, 재귀를 이용해 모든 경우의 수를 순회한다.
public int goodSolution(int k, int[][] dungeons) {
int answer = -1;
return dfs(k, dungeons);
}
int dfs(int k, int[][] dungeons) {
int cnt = 0;
for(int[] d : dungeons) {
int a = d[0], b = d[1];
if(a <= k) {
d[0] = 9999;
cnt = Math.max(1 + dfs(k - b, dungeons), cnt);
d[0] = a;
}
}
return cnt;
}
public static void main(String[] args) {
int[][] fares = {
{80,20},
{50,40},
{30,10}
};
number83 solution = new number83();
int result = solution.goodSolution(80,fares);
System.out.println(result);
}위 코드의 실행과정을 하나 하나 풀어보자면 아래와 같다.
{80, 20}, {50, 40}, {30, 10}, 80
{9999, 20}, {50, 40}, {30, 10}, 60 ------------------------------ +1------------------3----3
{9999, 20}, {9999, 40}, {30, 10}, 20 --------------------------- +1(1)--- | |
{9999, 20}, {9999, 40}, {30, 10}, 20 ----------------------- +0 |----2 |
{9999, 20}, {50, 40}, {9999, 10}, 50 ------------------------ +1(2)--- |
{9999, 20}, {9999, 40}, {9999, 10}, 10 -------------------- +1 |
|
{80, 20}, {9999, 40}, {30, 10}, 40 ------------------------------- +1(2)--------------2
{80, 20}, {9999, 40}, {9999, 10}, 30 --------------------------- +1(1) |
{80, 20}, {9999, 40}, {9999, 10}, 30 ----------------------- +0 |
|
{80, 20}, {50, 40}, {9999, 10}, 70 ------------------------------- +1(2)--------------2
{80, 20}, {9999, 40}, {9999, 10}, 30 --------------------------- +1(1)
{80, 20}, {9999, 40}, {9999, 10}, 30 ----------------------- +0
이렇게 하나하나 순회하며 최대로 갈 수 있는 던전의 수를 알 수 있다.
재귀에 대한 학습이 더 필요할 듯 하다.