[백준11727] / 2×n 타일링 2 - DP

2024. 7. 24. 16:13·Programming/Algorithm

 

백준 11727

 

 

푼 날짜 : 2024.07.24

푼 문제 : [11727] / 2×n 타일링 2

사용한 언어 : python

 

 

 

점화식:

dp[i] = dp[i−2]∗2+dp[i−1] (i≥2)

 

 

어떻게 구했냐면...

 

모를 땐 직접 그려보자

 

 

점화식 찾기..

(내)이해를 돕기위한 그림

 

 

(i-1) 에는 너비를 맞추기 위해 블록 하나(=> 2*1타일)씩을 붙일 수 있지만
(i-2) 에는 두 칸을 붙일 수 있으므로 x2를 해준다는 식으로 이해했다. (=> 2는 2*1타일과 2*2타일 두 개를 의미)

 

 

예를 들어 현재 주어진 수가 5라면 가로로 5칸을 차지한다.

이럴 경우 이전(i-1) 값인 4에는 1을 붙여야 5칸을 만들 수 있다.

그 이전(i-2) 값인 3에는 2를 붙여야 5칸을 만들 수 있다.

 

 

코드 :

import sys

N = int(sys.stdin.readline())
dp = [0 for _ in range(1000+1)]

dp[0] = 0
dp[1] = 1
dp[2] = 3
dp[3] = 5

for i in range(4, N+1):
    dp[i] = dp[i-2]*2 + dp[i-1]

print(dp[N]%10007)

 

 

+

이번 경우에는 

결과값만 바로 10007로 나누어 출력했다.

 

하지만 종종 수가 커지면 식이 맞아도 틀릴 수 있기 때문에

for i in range(4, N+1):
    dp[i] = (dp[i-2]*2 + dp[i-1])%10007

 

이렇게 계산 할 때 마다 나누어주는 것도 좋은 방법이다.

'Programming > Algorithm' 카테고리의 다른 글

[백준17219] / 비밀번호 찾기- 자료구조  (0) 2024.07.25
[백준14940] / 쉬운 최단거리 - 그래프(BFS)  (1) 2024.07.25
[백준11726] / 2×n 타일링 - DP  (0) 2024.07.24
[프로그래머스] [연습문제] / 추억 점수  (0) 2024.04.30
[프로그래머스] [연습문제] / 달리기 경주  (1) 2024.04.30
'Programming/Algorithm' 카테고리의 다른 글
  • [백준17219] / 비밀번호 찾기- 자료구조
  • [백준14940] / 쉬운 최단거리 - 그래프(BFS)
  • [백준11726] / 2×n 타일링 - DP
  • [프로그래머스] [연습문제] / 추억 점수
__narrrrrmm
__narrrrrmm
__narrrrrmm
낢
__narrrrrmm
글쓰기 관리
전체
오늘
어제
  • 분류 전체보기 (71)
    • Programming (68)
      • Algorithm (61)
      • React JS (2)
      • SQL (5)
    • 낢의 하루 (1)
    • 대외활동 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

백트레킹
React.js
파이썬
DP
heic
프로그래머스
mysql
다이나믹프로그래밍
백트래킹
최소스패닝트리
그래프
Javascript
알고리즘
BFS
백준
다익스트라
투포인터
PCCP
StarRating
DFS
MST
컬럼별칭
SQL
Python
누적합
파싱
삼성 금융아카데미
그래프탐색
Dijkstra
웹동아리
hELLO· Designed By정상우.v4.5.3
__narrrrrmm
[백준11727] / 2×n 타일링 2 - DP
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.