[백준] 1904번 : 01타일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1904번: 01타일

 

1. 문제 설명

2. 풀이과정

해당 문제는 길이를 입력받아 가능한 모든 2진 수열의 개수를 구하는 문제이다.

길이가 1일 때는 1가지, 2일 때는 2가지의 경우가 나온다.

해당 경우를 구하다 보면 각 경우의 수는 앞선 결과 2개를 더한 값이라는 것을 알게 된다.

0, 1, 2, 3, 5, 8, 13, 21,... 여기에서 해당 결과를 15746으로 나눈 값을 저장한다.

이를 활용해 원하는 길이까지의 경우를 저장하며 마지막으로 해당 길이의 경우의 수를 출력하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 길이를 입력받는다. N = int(sys.stdin.readline())
3. 길이의 최댓값인 1,000,000까지 저장 가능한 리스트를 생성한다.(각 인덱스 값이 길이) dp = [0] * 1000001
4. 길이가 1일 때 1의 결과를 저장하고 dp[1] = 1
5. 길이가 2일 때 2의 결과를 저장한다. dp[2] = 2
6. 길이가 3 이상일 때부터는 해당 길이까지 반복하며 for i in range(3, N + 1)
7. 해당 결과는 이전 2개의 결과를 더해 15746으로 나눈 값을 저장한다. dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
8. 해당 길이에 해당하는 결과를 출력한다. print(dp[N])

반응형

3. 소스코드

import sys

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

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3, N + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 15746

print(dp[N])