Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 2501
- 차세대 보안 리더 양성
- Best of the Best
- 5086
- 5586
- boj
- 4101
- 10995
- BoB 후기
- BOB
- 11109
- 11943
- 2605
- 차세대 보안 리더 양성 프로그램
- 공주대 정보보호
- 10833
- 2965
- EOF
- 정보보호 영재교육원
- 영재원
- 2476
- 영재교육원
- acmicpc
- 리뷰
- 1547
- Python
- 정보보호 영재원
- 2506
- text
- BoB 7기
Archives
- Today
- Total
짱해커가 되어보자
boj 2193 본문
문제
우선 이진수 중 다음의 특정 조건을 만족하는 경우 이친수라 하여, 해당 개수를 구하는 문제이다
- 맨 처음 앞자리가 무조건 1로 시작해야한다
- 연속된 1이 올 수 없다
입력
: N(1~90)출력
: N에 대한 이친수의 수
풀이
해당 조건을 만족해야할 경우 어떤 숫자이든 시작은 1이며, 다음에 이어오는 숫자는 0이어야 하므로10
이 기본 시작임을 알 수 있다
1의 경우 1. 1개
2의 경우 10. 1개
3의 경우부터 맨 뒷 바이트인 0,1 로 2개
4의 경우 3의 해당하는 경우와 2처럼 맨 앞이 10인 경우 3개.
5의 경우 4처럼 000, 001, 010의 경우와 3처럼 100, 101이 와야함을 알 수 있었다
e[i] = e[i-1] + e[i-2]
와 같은
단순 점화식 문제로 풀리는데, 내가 생각하는 이유는 다음과 같다
앞서 1과 연속되면 안되는다는 조건이 있다. i=6이라는 가정하에 생각해보면,
(10)????의 4자리 중 (10)0???는 5의 모든 케이스를 가져왔을 때 똑같이 일치한다
그러나 (10)1???는 바로 앞 ?에 1이 붙으면 안되므로, (i-2)즉 4의 케이스를 붙였을 때 연속되는 1이 아니므로 경우의 수가 일치한다
그러므로 e[i] = e[i-1] + e[i-2]의 점화식이 성립된다
e = [-1, 1, 1] + [0] * 88
n = int(input())
for i in range(3, n+1, 1):
e[i] = e[i-1] + e[i-2]
print(e[n])
Comments