코드업 codeup 4033 네모네모 로직

C언어

코드업 codeup 4033 네모네모 로직

mcdn 2021. 1. 20. 10:10

www.codeup.kr/problem.php?id=4033

네모네모 로직

[문제3] 네모네모 로직 (20점, 제한시간 1초) 네모네모 로직은 숫자를 이용하여 그림을 만드는 퍼즐로서 picross로 불리기도 한다. 아래의 그림에서 왼쪽이 15x15 크기의 퍼즐의 문제이다. 여기에 적

www.codeup.kr

문제 분류 : 보기

문제 설명 내 문제집에 추가 풀이1(C/C++) 내소스1

[문제3] 네모네모 로직 (20점, 제한시간 1초)

네모네모 로직은 숫자를 이용하여 그림을 만드는 퍼즐로서 picross로 불리기도 한다. 아래의 그림에서 왼쪽이 15x15 크기의 퍼즐의 문제이다. 여기에 적혀진 숫자는 연속해서 칠해야 하는 칸의 수를 나타낸다. 예를 들어, “4 3”은 4칸 연속해서 칠한 다음에 3칸을 연속해서 칠한다는 의미이다. 그러나 칠해진 4칸과 칠해진 3칸 사이에는 최소한 1개 이상의 칠해지지 않은 칸이 있어야 한다. 아래 그림의 왼쪽 문제에 대한 답은 오른쪽의 그림이다.

네모네모 로직에 흥미를 느낀 길동은 이 퍼즐을 컴퓨터 프로그램으로 풀어보기로 하고, 우선 하나의 줄에 대해서 몇 가지 경우가 있는지를 헤아려 보기로 하였다.

한 줄에 있는 칸의 수와 칠해야 되는 연속칸을 나타내는 수들이 입력되었을 때, 몇 가지의 경우가 가능한지를 구하는 프로그램을 작성하시오.

입력

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

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

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

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

출력

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

입력 예시 예시 복사

15 3 5 4 3

출력 예시

#include <iostream>
using namespace std;

int arr[20];
int cnt;

void	bck(int sum, int idx, int prev, int n, int k)
{
	//cout << sum << " " << idx << "   ";
	if (sum > n || idx > k)
		return ;
	else if (sum == n && idx < k )
		return ;
	if (sum == n && idx == k )
	{
		cnt++;
		//cout << "a ";
		return ;
	}
	if (prev == 0)
		bck(sum + arr[idx], idx + 1, 1, n, k);
	bck(sum + 1, idx, 0, n, k);
}


int main(void)
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < k; i++)
		cin >> arr[i];
	cnt = 0;
	bck(0, 0, 0, n, k);
	cout << cnt;
}