C ) 생일케이크 양초 끄기 문제

문제 ) 생일케이크에 n>0 개의 불켜진 양초가 원형으로 빙둘러 서있다. 첫 번째 양초부터 시작하여, k>0 개의 양초를 건너뛰어 나타나는 양초의 불을 끄고 뽑아낸다. 그리고는 다음 양초로부터 시작하여 k개의 양초를 건너뛰어 나타나는 양초의 불을 끄고 뽑아낸다. 원을 돌면서 양초가 하나만 남을 때까지 촛불 끄고 뽑아내기를 계속함.

 이 마지막 양초는 내부에 특수장치가 설치되어 있어서 불이 꺼짐과 동시에 멋진 축하쇼를 펼치도록 되어 있다. n과 k를 미리 알 경우, 원래 양초들의 원형 배치에서 특수 양초의 위치를 어디로 해놓아야 마지막까지 남을 지 알고 싶다.

 

=> 이 문제는 배열과 원형연결리스트를 각각 이용하여 풀이가 가능하다. 배열로 푸는 경우, 끈 촛불을 그대로 두고 계산하는 경우와 끈 촛불을 뺐다고 가정하는 경우로 나누어 풀이 가능함. C 를 사용하여 풀이.

 

 

배열로 풀이 한 경우

#include <stdio.h>
#include <stdlib.h>

//배열 문제

void buildList(int* A, int n)
{
	for (int i = 0; i < n; i++)
	{
		A[i] = i + 1;
	}
}

void removes(int* A, int n, int pos)
{
	for (int i = pos; i < n; i++)
		A[i] = A[i + 1];
}

//배열_ver1
int runSimulation(int* A, int n, int k)
{
	int r = 0;
	int num = n, N = n;
	while (num > 1)
	{
		int i = 0;
		while (i < k)
		{
			r = (r + 1) % N;
			if (A[r] != 0)
				i++;
		}
		A[r] = 0;
		num--;
		while (A[r] == 0)
			r = (r + 1) % N;
	}
	return A[r];
}

//배열_ver2
int runSimulation2(int* A, int n, int k)
{
	int r = 0, num = n;
	while (num > 1)
	{
		r = (r + k) % num;
		removes(A, num, r);
		num--;
	}
	return A[0];
}

int candle(int* A, int n, int k)
{
	buildList(A, n);

	return runSimulation2(A, n, k);
}

int main()
{
	int size;
	scanf_s("%d", &size);
	int* arr = (int*)malloc(sizeof(int)*size);
	int k;
	scanf_s("%d", &k);

	printf("%d", candle(arr, size, k));
	return 0;
}

위의 코드에서 runSimulation 함수는 끈 양초를 그대로 두는 경우, runSimulation2 는 끈 양초를 제거하는 경우이다.

candle 함수에서 사용할 함수에 맞춰 return 에서 호출하면 된다.

 

 

원형연결리스트를 사용한 경우

#include <stdio.h>
#include <stdlib.h>

//원형 연결리스트

typedef struct ListNode
{
	int data;
	struct ListNode* link;
}ListNode;

//헤더
typedef struct
{
	ListNode* head;
}LinkedListType;

LinkedListType buildList(int n)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	LinkedListType* L = (LinkedListType*)malloc(sizeof(LinkedListType));
	L->head = p;
	p->data = 1;
	for (int i = 2; i <= n; i++)
	{
		p->link = (ListNode*)malloc(sizeof(ListNode));
		p = p->link;
		p->data = i;
	}
	p->link = L->head;

	return *L;
}

int runSimulation(LinkedListType* L,int n,int k)
{
	ListNode* p = L->head;
	while (p != p->link)
	{
		for (int i = 1; i < k; i++)
			p = p->link;
		ListNode* pnext = p->link;
		p->link = p->link->link;
		free(pnext);
		p = p->link;
	}
	return p->data;
}

int candle(int n, int k)
{
	LinkedListType L = buildList(n);
	return runSimulation(&L, n, k);
}

void main()
{
	int size;
	scanf_s("%d", &size);
	int k;
	scanf_s("%d", &k);

	printf("%d", candle( size, k));

}

 

 

C는 동적할당을 매번 받는게 참 귀찮다. 아무래도 파이썬을 다시 공부해야할듯..