[C/C++] 코드업(codeup) 4033번 네모네모 로직

▽문제 바로가기

https://codeup.kr/problem.php?id=4033

네모네모 로직

---

입력

1. 첫째 줄에는 전체 칸의 수 n이 입력된다. (1≤n≤20)

2. 두 번째 줄에는 연속칸의 개수 k가 입력된다. (1≤k)

3. 세 번째 줄에는 k개의 자연수가 공백으로 분리되어 입력된다. 이 숫자들은 각각의 연속칸의 크기를 나타낸다.

4. 입력은 최소한 1개 이상의 경우를 만들 수 있는 수들이 입력된다. 즉, n이 15일 때 “10 2 2”와 같이 색 칠하기가 불가능한 수는 입력되지 않는다.

 

출력

1. 주어진 입력에 대하여 몇 가지의 칠하기가 가능한지를 하나의 정수로서 출력한다.

 

문제 풀이

 

쉬운 문제입니다. 주석참고.

#include <stdio.h>

int n;	//입력받을 정수n 
int k; 
int cnt = 0;
int arr[20] = {0,};	//출력용 배열

//백트래킹
//i : 전체칸수, count : k수, prev : 색칠칸여부
void backtracking(int i, int count, int prev){
	if(i>n) return;
	if(count>k) return;
	
	if(count==k&&i==n){
		cnt++;
		return;
	}
	
	if(prev==0) backtracking(i+arr[count], count+1, 1);	//전에 색칠칸없으면 색칠가능
	backtracking(i+1, count, 0);	//색칠안하고 그냥 한 칸
}


int main(){
	
	scanf("%d", &n);
	scanf("%d", &k);
	for(int i=0;i<k;i++) scanf("%d", &arr[i]);
	
	//백트래킹
	backtracking(0, 0, 0);
	
	printf("%d", cnt);
	
	return 0;
}