[백준] 2226 이진수 (골드 4)

1으로 시작하는 그룹의 개수를 구하는 것이 문제이지만, 이를 풀기 위해서 0으로 시작하는 그룹의 개수 또한 dp로 저장하며 계산에 활용했습니다. 찾아낸 패턴은 아래와 같습니다. 0으로 시작하는 이진수의 배열을 dp_0(n)이라 하고, 1로 시작하는 이진수의 배열을 dp_1(n)이라 하면 dp_0(n) = dp_0(n-2) + dp_1(n-2) + dp_0(n-1) dp_1(n) = dp_1(n-2) + dp_0(n-2) + dp_1(n-1) 여기서 + 연산은 파이썬에서의 문자열 concatenation 연산자로 사용했습니다. 0으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_0_group(n)이라 하고, 1으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_1_group(n)이라 하면 n이..

2023.05.14