백준 : 이친수(2193) with 파이썬

https://www.acmicpc.net/problem/2193

2193번: 이친수

문제

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로 시작하며 1이 두번연속으로 나타나지 않도록 설계하는 것이다.

그럼 n = 1, 2, 3, 4일 경우를 하나하나 대입해보면서 직관적으로 풀이를 해보도록 하겠다.

-----------------------------------------

N = 1일 경우(한자리수 이친수)

0 -> X ( 0으로 시작 불가) 

1 -> O

result = 1

-----------------------------------------

N = 2일 경우(두자리수 이친수)

00, 01 -> X ( 0으로 시작 불가) 

11 -> X ( 1 연속 불가)

10 ->  O

result = 1

-----------------------------------------

N = 3일 경우(세자리수 이친수)

000, 001, 010 -> X ( 0으로 시작 불가) 

110,111 -> X ( 1 연속 불가)

100, 101 -> O

result = 2

-----------------------------------------

N = 4일 경우(네자리수 이친수)

0000, 0001, 0010, 0100 -> X ( 0으로 시작 불가) 

1100,1110 -> X ( 1 연속 불가)

1000, 1010, 1001 -> O

result = 3

-----------------------------------------

dp로 위 이친수들을 정리해보면

dp[1] = 1

dp[2] = 1

dp[3] = 2

dp[4] = 3

현재 이친수 = 전이친수 + 전전이친수 

이런식으로 점화식을 계산할 수 있을것같다.

위 식을 코드로 짜면 result = (dp[i - 1] + dp[i-2]) 이런식으로하면 이친수의 값을 구할 수 있을것이다.

 

그럼 실제 코드를 보고 분석해보자

mport sys

input = sys.stdin.readline

n = int(input())

dp = [0, 1, 1]

for i in range(3, n + 1):

      result = dp[i - 1] + dp[i - 2]

      dp.append(result)

print(dp[n])

sys 모듈 : 시스템과 관련된 함수와 변수들을 제공하여 파이썬 프로그램이 운영 체제와 상호 작용하고 정보를 얻을 수 있게 도와줍니다.

sys.stdin

sys.stdin : sys 모듈 내에 있는 표준 입력 스트림을 나타내는 객체입니다. 표준 입력 스트림은 사용자가 키보드로 입력하는 데이터를 읽어오는 용도로 사용됩니다.

input = sys.stdin.readline

sys.stdin.readline : 표준 입력 스트림에서 한 줄을 읽어오는 함수입니다. 이 함수를 호출하면 사용자가 입력한 데이터 중에서 한 줄을 읽어와 문자열로 반환합니다. 입력이 없을 때까지 기다릴 수 있습니다.

----------------------------------------------------------------------------------------------------------------------

n = int(input())

n에 자릿수를 입력받습니다.

dp = [0, 1, 1]

dp 배열에 0, 1, 1을 저장해줍니다. dp[0, 1, 1]이 의미하는 것을 길게 풀어보면
dp[0] = 0

dp[1] = 1

dp[2] = 1

for i in range(3, n + 1):

      result = dp[i - 1] + dp[i - 2]

      dp.append(result)

아까 위에서 설명한 것처럼 dp[0], dp[1], dp[2]를 미리 정의한것입니다.

그럼이제 dp가 3보다 큰경우만 계산해주면 됩니다.

현재 이친수 = 전이친수 + 전전이친수 

        result = (dp[i - 1] + dp[i-2])

이제 result에 저장한 이친수를 dp에 append()함수를 써서 dp 리스트의 끝에 추가합니다.

print(dp[n])

최종적으로 dp[n]을 출력하면 n자리 이친수의 개수를 구할 수 있을 것입니다.