백준(baekjoon) 1904번: 01타일(실버 3, 파이썬 PYTHON) - 동적 계획법 1

문제

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

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

 

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

1904번: 01타일

 

import sys

N=int(sys.stdin.readline())
dp=[1]*(N+1)

dp[1]=1

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

print(dp[N])

 

※ 동적 계획법 1

 

 

● 먼저 1로 초기화 되어있는 크기가 N+1 인 배열 dp를 만들어준다. (각 숫자 크기 그대로 인덱스에 접근하기 위함)

 

● N이 1이면 타일 1 만 만들 수 있으므로 dp[1]에 1값을 저장해준다.

 

● 그 후 규칙을 잘 찾아보면 

 

N이 짝수일 때

-> N-1 은 홀수이고, 이 때 만들어 질 수 있는 타일 뒤에 1을 붙이면 크기가 N인 타일들이 만들어진다.

-> N-2 는 짝수이고, 이 때 만들어 질 수 있는 타일 뒤에 00을 붙이면 크기가 N인 타일들이 만들어진다. (11을 붙이면 위의 case와 겹치게 된다.)

 

N이 홀수일 때

-> N-1 은 짝수이고, 이 때 만들어 질 수 있는 타일 뒤에는 1을 붙이면 크기가 N인 타일들이 만들어진다.

-> N-2 는 홀수이고, 이 때 만들어 질 수 있는 타일 뒤에는 00을 붙이면 크기가 N인 타일들이 만들어진다. (11을 붙이면 위의 case와 겹치게 된다.)

 

● 결국, 각 인덱스 3 이상의 dp 요소의 값은 그 전 인덱스 요소 값과 그 전전 인덱스 요소 값의 합과 같다는 결론이 나온다.(인덱스 2 요소는 값이 2 이므로 for문을 같이 돌려주기 위해 dp 배열의 초기값을 1로 설정한 것이다.)

 

 

결과

 

 

♣ 참고: 동적계획법

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키