BOJ 2193 이친수

4755 단어 2021.01.142021.01.14

https://www.acmicpc.net/problem/2193
시간 2초, 메모리 128MB
input :

  • N (1 ≤ N ≤ 90)

output :

  • N자리 이친수의 개수를 출력

조건 :

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

0으로 시작하지 않으니까
길이가 1일 때는 1 한 개.

숫자가 0으로 끝날 때 / 숫자가 1로 끝날 때 두 경우를 이용해 변수를 저장하자.

위의 방식을 N번 진행해서 current 리스트 안의 값들을 더해주면 개수를 구할 수 있다.

1번 부터 시작하기때문에 N - 1번 실행 한다.

import sys

n = int(sys.stdin.readline())

previous = [0, 1]
current = [0, 0]

for i in range(n - 1):
    current[0] = previous[1]
    current[0] += previous[0]
    current[1] = previous[0]

    previous[0] = current[0]
    previous[1] = current[1]

print(sum(previous))

내가 푼 방법도 스와핑이다. 이를 변수 2개만 시용해서도 풀 수 있다는 것 알아두자.

a, b = 1, 1
for i in range(int(input())-2):
    a,b=b,a+b
print(b)

좋은 웹페이지 즐겨찾기