계단오르기

Question

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int cnt = 0; public static void dfs(int sum, int n) { int[] arr = {1, 2}; for (int i = 0; i < arr.length; i++) { sum += arr[i]; if (sum == n) { cnt++; sum -= arr[i]; } else { if (sum < n) dfs(sum, n); sum -= arr[i]; } } } public static void main(String[] args) throws Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(bufferedReader.readLine()); dfs(0, n); System.out.println(cnt); } } dp를 잘 몰라서 자력으로 dfs 방식으로 풀었는데 그닥 좋지 않은 접근일까요...?

김태원 · Answer

안녕하세요^^ 거의 모든 출제자가 dp 문제를 DFS 풀면 100% 타임리밋 나도록 문제와 테스트케이스를 설계합니다. dp 문제는 다이나믹으로 푸는 습관을 들여야 합니다. DFS로 푸는 습관을 들였다가는 dp 문제를 봐도 DFS로 밖에 생각나지 않습니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 계단 오르기 문제를 DFS(Depth First Search)로 풀이하는 것은 가능합니다. 그러나, 이 방법은 계산량이 많아질 수 있는 문제를 가지고 있습니다. DFS 방식으로 모든 가능한 경로를 탐색하려다 보니, 계단 수가 커질수록 시간 복잡도가 기하급수적으로 증가할 수 있습니다. 따라서, DFS는 작은 입력에 대해선 잘 작동하지만, 큰 입력에서는 비효율적일 수 있습니다. 계단 오르기 문제는 일반적으로 동적 프로그래밍(DP) 기법을 사용하여 해결하는 것이 효율적입니다. DP를 사용하면 이전 계산된 결과를 활용하여 중복 계산을 줄일 수 있습니다. 이를 통해 시간 복잡도를 많이 개선할 수 있습니다. 관련 질문 URL: - 계단오르기 질문 - 이 질문에서는 DFS로 문제를 해결했을 때의 한계점에 대해 논의하고 있으며, 계단의 수가 많아질수록 시간초과 문제가 발생할 수 있음을 다루고 있습니다. 지속적으로 동적 프로그래밍 기법을 연구해보는 것도 좋은 접근입니다. 필요시 DP에 대한 기초와 응용을 다룬 자료를 학습하시면 문제를 해결하는 데 많은 도움이 될 것입니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.