문제
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
알고리즘
- dp를 통해 타일이 n개일 때의 규칙을 찾아 점화식을 도출해 낸다.
- 점화식 : f(n) = f(n - 1) + f(n - 2)
- 반복문을 통해 점화식을 표현한다.
코드
import sys
n = int(sys.stdin.readline())
dp = [0] * 1000001
dp[1] = 1 # 1
dp[2] = 2 # 00, 11
dp[3] = 3 # 100, 001, 111,
# dp[4] = 5 # 0011, 1100, 1001, 0000, 1111
# dp[5] = 8 # 00001, 00100, 10000, 11100, 00111, 11001, 10011, 11111
# dp[6] = 13 # 000011, 001100, 110000, 100001, 100100, 001001, 001111, 110011, 111100, 111001, 100111, 111111, 000000
# 반복문을 통해 점화식을 표현
# 점화식 : f(n) = f(n - 1) + f(n - 2)
for i in range(4, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
print(dp[n])github
GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법
내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by creating an account on GitHub.
github.com
'CodingTest > Baekjoon' 카테고리의 다른 글
| [baekjoon] 백준 11057번(파이썬): 오른막 수 (0) | 2021.12.06 |
|---|---|
| [baekjoon] 백준 9465번(파이썬): 스티커 (0) | 2021.12.05 |
| [baekjoon] 백준 11052번(파이썬): 카드 구매하기 (0) | 2021.12.03 |
| [baekjoon] 백준 1010번(파이썬): 다리 놓기 (0) | 2021.12.02 |
| [baekjoon] 백준 14501번(파이썬): 퇴사 (0) | 2021.12.02 |