문제링크: https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
작성코드
풀이
규칙을 알아보기 위해 우선 4까지 직접 작성해보자.
# dp[N]
dp[1] = 1
dp[2] = 00, 11
dp[3] = 001, 111, 100
dp[4] = 0011, 1111, 1001, 0000, 1100
일부러 규칙이 보이는 순서로 dp[4]를 작성하였다.
기존의 수열에서 다른 수를 뒤에 붙혀주면 서로 다름을 유지하면서 새로운 수가 완벽하게 생성된다.
1을 추가하는 경우와 00을 추가하는 경우를 생각할 수 있는데 1을 추가하기 위해서는 한칸이 필요하므로
dp[N-1]에서 붙혀주고 00을 추가하기 위해서는 dp[N-2]에서 붙혀준다.
이를 코드로 작성해보면
이와 같이 나온다.
※ 이때 15746을 나눠주는 이유는 메모리에 들어가는 값이 너무 커지는 것을 방지하기 위해 문제 외적으로 백준에서 요구한 지정 값이다.
'백준 > Python' 카테고리의 다른 글
| [백준] 11659 구간 합 구하기 (python 파이썬) (0) | 2022.11.24 |
|---|---|
| [백준] 1149 RGB거리 (python 파이썬) (0) | 2022.11.16 |
| [백준] 9184 신나는 함수 실행 (python 파이썬) (0) | 2022.11.09 |
| [백준] 24039 2021은 무엇이 특별할까? (python 파이썬) (0) | 2022.11.07 |
| [백준] 25707 팔찌 만들기 (python 파이썬) (0) | 2022.11.07 |