알고리즘 1

N자리 이진수가 있고, K개의 1이 있다고 할 때
이 수들 중 3의 배수인 것의 개수를 구하여라

동적할당으로 풀어야 함

#include <stdio.h>
const int N = 30;
const int K = 20;
int arr[N+1][K+1][3]; //재계산하지 않도록 배열에 저장
int f(int n, int k, int r) { // nbit에서 k개가 1인 3n+r 형태의 갯수
	// 여기에 이미 계산해 놨으면 바로 배열에서 찾아서 return
	if (arr[n][k][r] != -1)
		return arr[n][k][r];

	// n-1 , k-1 이용해서 호출 해서 계산
	if (k==0) { // 0000000
		if (r == 0) return 1;
		else return 0;
	}
	if (k == n) { // 11111...111
		if (n % 2 == 0)
			if(r==0) return 1;
			else return 0;
		else
			if (r == 1) return 1;
			else return 0;
	}
	// 최상위 bit 0인 경우 세보자
	int ret = f(n - 1, k, r);
	int R = (n  % 2 == 1)? 1 : 2;

코드 설명 :

	int R = (n  % 2 == 1)? 1 : 2; 

1000 일 경우 8로 + 1 을 해야 3의 배수가 됨
10000 일 경우 16으로 +2를 해야 3의 배수
.
.
.
자리수가 n%2==0 일 경우 +2를 해야 3의 배수
자리수가 n%2==1 일 경우 +1을 해야 3의 배수

	int s = (3  - R + r) % 3; // 무조건 0,1,2
	ret += f(n - 1, k - 1, s);
	arr[n][k][r] = ret;
	return ret;
	
}
int main() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			for (int r = 0; r < 3; r++) {
				arr[i][j][r] = -1; 
			}
		}
	}
	scanf("N: %d   K: %d", &N, &K);
    printf("%d", f(N, K, 0));
	return 0;
	
}

이렇게 재귀함수와 동적 계획법을 사용할 경우 계산을 줄일 수 있게 된다