[백준 2193 파이썬/python] 이친수

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

이친수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	84598	35637	26936	40.573%

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1

3

예제 출력 1

2

풀이

1)

d = [0]*91
n = int(input())
d[1] = 1
d[2] = 1
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])

피보나치 수열은 이전 두 수의 합으로 나타나는 수열로, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...와 같은 형태를 가집니다. 코드를 한 줄씩 살펴봅시다.

1. d = [0]*91: 길이가 91인 리스트를 생성하고, 모든 원소를 0으로 초기화합니다. 이 리스트는 계산된 피보나치 수를 저장하는 데 사용됩니다.

2. n = int(input()): 사용자로부터 입력을 받아 정수로 변환한 후, 변수 n에 저장합니다. n은 피보나치 수열의 n번째 항을 구하기 위한 값입니다.

3. d[1] = 1: 피보나치 수열의 첫 번째 항(1)을 리스트 d의 인덱스 1에 할당합니다.

4. d[2] = 1: 피보나치 수열의 두 번째 항(1)을 리스트 d의 인덱스 2에 할당합니다.

5. for i in range(3, n+1):: 3부터 n까지 반복합니다. 이 반복문은 피보나치 수열의 3번째 항부터 n번째 항까지를 계산하는 데 사용됩니다.

6. d[i] = d[i-1] + d[i-2]: 현재 인덱스(i)의 피보나치 값을 구하기 위해 이전 두 개의 피보나치 값(d[i-1]과 d[i-2])을 더하고 결과를 리스트 d의 i번째 인덱스에 저장합니다.

7. print(d[n]): n번째 피보나치 값을 출력합니다.

이 코드를 실행하면, 사용자가 입력한 n에 대한 피보나치 수열의 n번째 항을 출력합니다.

Uploaded by N2T