[백준 1003 실버3] 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

해결방안

• DP를 이용하여 해결

알고리즘

1. n이 0 혹은 1일 경우는 미리 출력하고 종료시켜버림

2. dp는 [0, 0] 리스트로 구성된 n + 1 크기의 리스트 생성 (2차원)
   • dp를 리스트로 지정하는 이유는 0과 1의 갯수를 별도로 카운팅 하기 위함
3. dp[0]과 dp[1] 값을 지정
   1. dp[0]에는 0의 값은 1, 1의 값은 0을 나타내도록 [1, 0] 리스트를 할당
   2. dp[1]에는 0의 값은 0, 1의 값은 1을 나타내도록 [0, 1] 리스트를 할당
4. 피보나치와 동일하게 인덱스는 2부터 n번째까지 dp 수행
5. 점화식에 따라 값을 더함
   1. i - 1의 원소가 있을 수 있다는 것이므로 그때 원소의 0과 1의 값을 현재값에 더해줌
   2. i - 2의 원소가 있을 수 있다는 것이므로 그때 원소의 0과 1의 값을 현재값에 더해줌
6. dp[n]의 값을 출력

핵심 팁

• 우선 그림을 그려보며 반복되는 부분을 표시해보며 찾음
• 그림을 그려보면 특정 하위 부분이 계속 반복된다는 것을 찾을 수 있음
  • 즉, 이전에 나타났던 횟수를 현재에 추가하면 된다는 의미
  • 혹은 표로 나타내어봐도 점화식을 찾을 수 있음
• 점화식
  • dp[i] = dp[i - 1] + dp[i - 2]
    • 이전에 i - 1에서 카운팅 했던 값들을 현재 i에서도 카운팅 할 수 있다는 의미
    • 이전에 i - 2에서 카운팅 했던 값들을 현재 i에서도 카운팅 할 수 있다는 의미
  • dp[i]에 값을 씌우는 것이 아닌 더하는 이유는 이전에 dp[i]값이 업데이트 될 수 있기 때문이다.

 

t = int(input())
def fibonacci(n):
    # 0일 경우에는 그냥 1 0 출력하고 종료
    if n == 0:
        print(1, 0)
        return
    # 1일 경우에는 그냥 0 1 출력하고 종료
    if n == 1:
        print(0, 1)
        return
    # n까지 채울 수 있도록 n + 1 크기로 초기화 시켜줌
    dp = [[0, 0] for _ in range(n + 1)]
    dp[0] = [1, 0]
    dp[1] = [0, 1]
    # 피보나치처럼 2부터 n까지 순환
    for i in range(2, n + 1):
        # 조건을 지정할 필요 없음 2부터 시작하기 때문에 애초에 i - 1과 i - 2의 값을 가지고 있음
        dp[i][0] = dp[i - 1][0] + dp[i - 2][0]
        dp[i][1] = dp[i - 1][1] + dp[i - 2][1]
    print(" ".join(map(str, dp[n])))
for _ in range(t):
    n = int(input())
    fibonacci(n)

 

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public