[알고리즘] 백준 1904번 - 01타일

Question

문제 분석 결과 1, 2, 3, 5, 8, 13,....이렇게 진행되는 피보나치 수열임을 알았고, 아래와 같이 코드를 작성하였습니다. 이클립스 확인 결과 10000까지는 정상 실행되는 것 같은데 20000으로 테스트 해보니 stackoverflow 발생하네요. 다른 사람들 풀이를 찾아봐도 저랑 크게 다르지 않은 것 같은데 뭐가 문제인지 모르겠습니다. 원인과 해결방법을 아시는 분들 댓글 부탁드려요 import java.util.Scanner;public class Main { static int[] dp &#61; new int[1000001]; public static int arr_tile(int num) { if(dp[num] > 0) { return dp[num]; } if(num <&#61; 2) { return num; } else { dp[num] &#61; (arr_tile(num-2) &#43; arr_tile(num-2)) % 15746; return dp[num]; } } public static void main(String[] args) { Scanner sc &#61; new Scanner(System.in); int num &#61; sc.nextInt(); System.out.println(arr_tile(num)); } //end main }

defectio · Answer

중간에 else절 안에 오타 수정하겠습니다.dp[num] &#61; (arr_tile(num-2) &#43; arr_tile(num-2)) % 15746; 에서dp[num] &#61; (arr_tile(num-1) &#43; arr_tile(num-2)) % 15746; 로 수정하겠습니다.

리을 · Answer

dp 배열에 이전 값을 저장 했으니 저장한 값들을 이용해서 현재 구하고자 하는 값을 찾는 게 재귀호출을 사용하는 것보다 낫지 않을까요? dp[num] &#61; (dp[num-1] &#43; dp[num-2]) % 15746메모이제이션에 대해서 알아보시면 좋을 거 같습니다.

defectio · Answer

dp 배열에는 초기값으로 0이 저장되어 있는거 아닌가요??랭벋님 말대로 dp[num] &#61; (dp[num-1] &#43; dp[num-2]) % 15746; 를 적용해보면예를들어, 매개값으로 10이 전달되었다고 했을 때,즉, num &#61;&#61; 10 일 때, dp[10] &#61; (dp[9] &#43; dp[8]) % 15746; 이 실행 될텐데 여기서 dp[9], dp[8] 은 0이지 않나요??그리고 top-down 방식으로 풀려고 하면 재귀호출 &#43; 메모이제이션 사용해야 되는거 아닌가요???

리을 · Answer

죄송합니다. 제가 코드를 제대로 읽지 않았네요. defectio님 코드를 바탕으로 수정해봤습니다. 참고가 되시면 좋겠어요. 파이썬 코드import sys n &#61; int(sys.stdin.readline()) dp &#61; [0] * 1000001 def tile(num: int): global dp if num < 2: dp[num] &#61; 1 return dp[num] else: dp[num] &#61; (dp[num-1] &#43; dp[num-2]) % 15746 return dp[num] for i in range(n&#43;1): tile(i) print(tile(n)) 자바 코드import java.util.Scanner; public class Main { static int[] dp &#61; new int[1000001]; public static int arr_tile(int num) { if (num < 2) { dp[num] &#61; 1; return dp[num]; } else { dp[num] &#61; (dp[num-1] &#43; dp[num-2]) % 15746; return dp[num]; } } public static void main(String[] args) { Scanner sc &#61; new Scanner(System.in); int num &#61; sc.nextInt(); for (int i &#61; 0; i <&#61; num; i&#43;&#43;) { arr_tile(i); } System.out.println(arr_tile(num)); } }

[알고리즘] 백준 1904번 - 01타일

4개의 답변

Q&A 목록