[백준] 1003 - 피보나치 함수 (Python, 숏코딩 포함)

BAEKJOON's Logo

 

1003번: 피보나치 함수

Contents

---

* 일반 풀이와 숏코딩 풀이

## 일반 풀이
def fib(N):
    zeros=[1,0,1]
    ones=[0,1,1]
    if N >= 3:
        for i in range(2,N):
            zeros.append(zeros[i-1] + zeros[i])
            ones.append(ones[i-1] + ones[i])
    print(f"{zeros[N]} {ones[N]}")

T = int(input())
for _ in range(T):
    N = int(input())
    fib(N)

## 숏코딩 풀이
T = int(input())
for _ in range(T):
    N = int(input())
    zero,one=1,0 # zero: 0개수, one: 1개수
    for i in range(N):
        zero,one = one,zero+one # zero와 one에 대해 피보나치적용
    print(zero,one)

 

문제 정의

문제에서 입력으로 반복할 테스트 케이스 수 T가 주어지고, 다음 줄부터 T 만큼 N 이 주어집니다. 이때, 주어진 각 N에 대해 문제에서 주어진 fibonacci 함수를 적용했을 때, 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력합니다.

예제 입력 및 출력

 

일반 풀이와 숏코딩 풀이

일반 풀이

def fib(N):
    zeros=[1,0,1] # 0이 출력되는 횟수 리스트
    ones=[0,1,1] # 1이 출력되는 횟수 리스트
    if N >= 3:
        for i in range(2,N):
            zeros.append(zeros[i-1] + zeros[i])
            ones.append(ones[i-1] + ones[i])
    print(f"{zeros[N]} {ones[N]}")

T = int(input())
for _ in range(T):
    N = int(input())
    fib(N)

먼저, 테스트 케이스 개수를 T에 입력받습니다. for문으로 T만큼 반복하며, N을 입력받고, fib함수에 인자로 넣습니다. 핵심은, fib함수입니다. zeors는 0이 출력되는 횟수를 저장하는 리스트입니다. 예를들어, N이 0이면, 0이 1개이므로 zeros[0]은 1입니다. N이 1이라면 fibonacci함수의 결과에서 0이 출력되는 횟수는 0번일 것이므로, zeors[1]은 0입니다. 이때, N에 따라 0이 출력되는 횟수인 zeros와 1이 출력되는 횟수인 ones 역시 피보나치 수열의 패턴을 갖는다는 것이 핵심입니다. 그래서, fib함수에서 N이 주어지면 처음 0,1,2 일때는 리스트에 저장해 두고, 그 이상인 경우 range(2, N) 동안 zeros.append(zeros[i-1] + zeros[i])를 통해 zeros를 피보나치수열대로 추가해가며, ones도 마찬가지입니다. 그리고 N번째에 대해 0이 출력되는 횟수 zeros[N]과 1이 출력되는 횟수 ones[N]을 print 하고 함수는 종료됩니다.

 

숏코딩 풀이

T = int(input())
for _ in range(T):
    N = int(input())
    zero,one=1,0 # zero: 0개수, one: 1개수
    for i in range(N):
        zero,one = one,zero+one # zero와 one에 대해 피보나치적용
    print(zero,one)

위와 마찬가지로 T와 N을 입력받습니다. 여기서 숏코딩 풀이의 핵심 원리는 zeros와 ones가 같은 피보나치수열에 있다는 것입니다. 위 풀이에서 0이 출력되는 횟수의 규칙은 1,0,1,1,2,3,... 입니다. 1이 출력되는 횟수의 규칙은 0,1,1,2,3,... 입니다. 자세히 보면 0이 출력되는 횟수의 2번째 이후가 1이 출력되는 횟수의 규칙과 같음을 알 수 있습니다. 이를 이용해 0이 출력되는 횟수를 zero에, 1이 출력되는 횟수를 one에 저장하여 zero, one = one, zero+one으로 피보나치수열을 한 칸씩 이동하는 것이 핵심적인 코드 부분입니다.

 

읽어주셔서 감사합니다.

오늘도 발전하는 독자 여러분을 응원합니다.

다음에 더 유익하고 재미있는 포스팅으로 찾아오겠습니다.

 

* 아래 깃허브에 해당 풀이를 정리해 두었습니다.

GitHub - netsus/BaekJoon: Algorithm Problem solving