«   2022/06   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    
Archives
Today
45
Total
86,235
관리 메뉴

차근차근

[백준 1904] 01타일 본문

대학교/Algorithm

[백준 1904] 01타일

SWKo 2020. 9. 10. 23:25

0. 제목

  • 백준 1904 01타일
  • BOJ 1904 01타일
  • 파이썬 1904 01타일
  • Python 1904 01타일

1. 문제

www.acmicpc.net/problem/1904

 

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이��

www.acmicpc.net


2. 풀이

  • dp[1] -> 0 -> 1개
  • dp[2] -> 00, 11 -> 2개
  • dp[3] -> 001, 100, 111 -> 3개 -> dp[2]에서 가장 뒤에 1추가 + dp[1]에서 가장 뒤에 00 추가
  • dp[4] -> dp[3]에서 가장 뒤에 1추가 + dp[2]에서 가장 뒤에 00 추가
  • dp[5] -> dp[4]에서 가장 뒤에 1추가 + dp[3]에서 가장 뒤에 00 추가
  • dp[n] -> dp[n-1]에서 가장 뒤에 1추가 + dp[n-2]에서 가장 뒤에 00 추가 ➡ dp[n] = dp[n-1] + dp[n-2]
  • 수가 너무 커지기 때문에 마지막에 15746으로 나눈 나머지를 출력하면 안되고 반복문 루프마다 15746으로 나눈 나머지를 구한다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
= int(input())
 
dp = [0* 1000001
 
dp[1= 1
dp[2= 2
 
for i in range(3, n + 1):
    dp[i] = (dp[i - 2+ dp[i - 1]) % 15746
 
print(dp[n])
 
 
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11053] 가장 긴 증가하는 부분 수열  (0) 2020.09.12
[백준 12865] 평범한 배낭  (0) 2020.09.11
[백준 1904] 01타일  (0) 2020.09.10
[백준 1325] 효율적인 해킹  (0) 2020.09.09
[백준 1012] 유기농 배추  (0) 2020.09.08
[백준 2606] 바이러스  (0) 2020.09.08
0 Comments
댓글쓰기 폼