Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 깃 연동
- 자바
- 모두의 네트워크
- 모두를위한딥러닝
- 리액트 네이티브 시작하기
- 스터디
- 팀플회고
- 데이터베이스
- 네트워크
- 백준 5525번
- 리액트 네이티브 프로젝트 생성
- 백준
- SQL
- 머신러닝
- HTTP
- 지네릭스
- React Native
- 데베
- 깃허브 토큰 인증
- 딥러닝
- 깃 터미널 연동
- 백준 4358번
- 백준 4358 자바
- 정리
- 백준 4949번
- 모두의네트워크
- 깃허브 로그인
- 문자열
- 리액트 네이티브
- 모두를 위한 딥러닝
Archives
- Today
- Total
솜이의 데브로그
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는 동적할당을 매번 받는게 참 귀찮다. 아무래도 파이썬을 다시 공부해야할듯..