2193 (1) 썸네일형 리스트형 [백준] 2193 - 이친수 아이데이션연속해서 숫자를 배열하는 문제를 풀어서 그런가 보자마자 2차원 dp로 풀어야겠다고 생각한 문제였다.사실 숫자가 0과 1밖에 없어서 1차원 dp 만으로도 풀리는 문제긴 하다!!왜그런지 좀 더 자세히 살펴보자문제에서 주어진 조건은 총 두개이다.1. 0으로 시작하지 말 것2. 1이 두번 연속으로 배열되지 말 것 이 말은 이렇게도 바꿀 수 있다.n자리 수의 i번째 자리의 숫자를 넣을 때,1. 1번째 자리는 1만 넣을 것2. i - 2까지의 경우의 수에서 01을 넣거나,i - 1까지의 경우의 수에서 0을 넣을 것이 관계를 수식으로 나타내면 다음과 같다cache[i] = cache[i - 2] + cache[i - 1] 풀이 n = int(input())cache = [[0] * (n + 1) for _ .. 이전 1 다음
