-
https://www.acmicpc.net/problem/1003
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201003
해당 문제는 피보나치 수에서 나오는 0과 1의 값을 출력해 주는 문제다
처음에 c++ 함수 재귀로 짠 소스가 있길래 해당 소스처럼 JAVA를 이용해 짜서 제출했더니
시간 초과가 발생하였다.
그래서 문제 분류를 보니 DP인 걸 알 수 있었고
DP를 이용해 해결했다.
해당 문제의 DP 식은 간단했다
N의 0의 개수 = N-1의 0의 개수 + N-2 0의 개수
N의 1의 개수 = N-1의 1의 개수 + N-2 1의 개수
DP를 2차원 배열로 구현했고 처음 0과 1의 데이터는 삽입해 주고
2부터 40까지 반복문을 돌면서 데이터를 다 넣어주고
입력받는 데이터 값에 대해서만 출력해 주었다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 17219 비밀번호 찾기 JAVA (0) 2021.11.10 Baekjoon 11726 2xn 타일링 JAVA (0) 2021.11.10 Baekjoon 1764 듣보잡 JAVA (0) 2021.11.10 Baekjoon 11724 연결 요소의 개수 JAVA (0) 2021.11.10 Baekjoon 1927 최소 힙 JAVA (0) 2021.11.10 댓글