2698
-
백준 2698번 인접한 비트의 개수 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 30. 20:21
이 글은 백준 알고리즘 문제 2698번 "인접한 비트의 개수" 를 풀이한다.풀이 방법으로는 동적계획법을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2698 0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를 들..