m개의 main dish 와 n개의 side dish 가 있다.
main dish 와 side dish 는 중복선택 불가하다고 할 때, main dish 와 side dish 로 가능한 모든 조합을 구해보자.
예를 들어, 2개의 main dish와 3개의 side dish가 있다면,
경우의 수는 3x2 = 6 이고, 모든 경우의 수는
{(m1, s1), (m2, s2)}
{(m1, s1), (m2, s3)}
{(m1, s2), (m2, s1)}
{(m1, s2), (m2, s3)}
{(m1, s3), (m2, s1)}
{(m1, s3), (m2, s2)}
for (int m1=s1; m1<=s3; m1++)
for (int m2=s1; m2<=s3; m2++)
if (m1==m2) continue;
printf("(m1, %d), (m2, %d)", m1, m2)
3개의 main dish와 3개의 side dish가 있다면, 3x2x1 = 6가지 경우이며,
{(m1, s1), (m2, s2), (m3, s3)}
{(m1, s1), (m2, s3), (m3, s2)}
{(m1, s2), (m2, s1), (m3, s3)}
{(m1, s2), (m2, s3), (m3, s1)}
{(m1, s3), (m2, s1), (m3, s2)}
{(m1, s3), (m2, s2), (m3, s1)}
for (int m1=s1; m1<=s3; m1++)
for (int m2=s1; m2<=s3; m2++)
if (m1==m2) continue;
for (int m3=s1; m3<=s3; m3++)
if (m3==m1 || m3==m2) continue;
printf("(m1, %d), (m2, %d), (m3, %d)", m1, m2, m3)
for loop 로 구현하면 m,n 값에 맞게 일일이 iterator 변수를 추가해주어야 하는 문제가 있음.
main dish2는 main dish1과 조합을 이루지 않은 side dish 중 한 개,
main dish3은 main dish1, main dish2와 조합을 이루지 않은 side dish 중 한 개 이므로
재귀로 구현해보면, 아래와 같음. (좀 더 간결하게 되려나)
#include <stdio.h>
void select(int id, int selected[3])
{
if (id == 2) {
int temp;
for (int iter = 0; iter < 3; iter++) {
if (selected[iter] == -1) {
temp = iter;
break;
}
}
selected[temp] = id;
for (int iter = 0; iter < 3; iter++) {
printf("(%d %d) ", iter, selected[iter]);
}
printf("\n");
selected[temp] = -1;
return;
}
for (int iter = 0; iter < 3; iter++) {
if (selected[iter] == -1) {
selected[iter] = id;
select(id+1, selected);
selected[iter] = -1;
}
}
}
int main()
{
int selected[3] = {-1, -1, -1};
select(0, selected);
return 0;
}
printf 부분 대신 다른 로직을 넣으면 permutation 경우의 수마다 특정 처리를 하는게 가능해보임. 예를 들면, main dish + side dish 조합 중 가장 가격이 싼 경우를 구할 때, printf 대신에 lowest_total_price 를 갱신하도록 하면 됨.
일단 코드를 좀 더 간결하게 하는 게 필요함.
또한 재귀 깊이가 어느 정도까지 가능한 지도 업데이트 할 것.
