[Algorithm] 수제 버거 장인 (SW Expert Academy – 3421)

출처

  • https://www.swexpertacademy.com

난이도

  • (하) – 중 – 상 – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • 여러 개의 재료를 사용하여 햄버거를 만들려고 한다. 하지만, 같이 사용하면 안되는 재료의 종류가 주어질 때 총 만들 수 있는 햄버거의 가짓수를 계산하는 문제이다.
  • SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

  • 처음에 읽고 모든 가짓수를 계산하기 위해서 Recursive 함수와 Cache (메모이제이션)을 사용하여 문제를 풀려고 생각해보았다. 하지만, 구현 방법이 바로 머리에 생각나지 않아서, 단순히 For Loop을 사용하여 모든 가짓수를 계산하는 코드를 작성했다.
  • 총 N개의 재료가 주어질 때 총 만들 수 있는 햄버거의 개수는 0부터 1 << N (1을 N 번 Shift 한 결과)까지이다. 이중 특정 재료가 들어간 햄버거를 제외하고 싶은 경우 &(And) 연산을 통하여 해당 Bit가 동시에 켜져 있는 경우를 제외하였다. 다행히 해당 방법으로 간단히 문제를 해결 할 수 있었다.
  • 생각보다 문제는 쉽게 풀렸는데 역시나 제일 빠른 코드 대비 성능이 상당히 느리다. 본 문제는 분명히 수학적으로 쉽게 접근하는 방법이 있는 것 같다. 제일 빠른 답안의 경우 대략 1ms 이내에 결과를 계산하는 것 같다. 역시나 알고리즘을 잘하기 위해서는 수학적 지식이 많이 필요한 것 같다.

코드 (본 문제 부터는 코드를 Github에 업로드 할 계획입니다. 주소: https://github.com/mkblog-cokr/algorithmCode)

  • For Loop을 사용하여 모든 경우의 수를 계산하는 코드
  • 실행 시간: 167ms (제일 빠른 코드 대비 대략 167배 (1ms) 느림)
//MK: 수제 버거 장인 문제 해결 코드
//MK: 모든 방법을 다 찾아보고 문제를 해결하는 방법

#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함
#pragma warning(disable:4996)

#define MAXCOM 400

int inputSize;
int numCom;
int combination[MAXCOM];

int main(void)
{
	int testCase;
	//MK: input.txt 파일에서 입력 읽기
	//freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++)
	{
		scanf("%d %d", &inputSize, &numCom);
		for (int i = 0; i < numCom; i++) {
			int tmp1, tmp2;
			scanf("%d %d", &tmp1, &tmp2);
			combination[i] = (1 << tmp1-1) | (1 << tmp2-1);
		}
		//MK: 모든 가능한 조합을 찾아보고 조합이 안되는 부분은 제거하는 코드
		int ret = 1 << inputSize;
		for (int i = 0; i < (1 << inputSize); i++) {
			for (int j = 0; j < numCom; j++) {
				int tmp = i & combination[j];
				if (tmp == combination[j]) {
					ret--;
					break;
				}
			}
		}
		printf("#%d %d\n", m, ret);
	}
	return 0;
}

 

Leave a Comment