시나브로

길이가 Lcm 인 장대 위를 N마리의 개미가 초당 1cm의 속도로 걷고 있습니다 .개미는 장대의 끝에 도착하면 장대의 및으로 떨어집니다. 또한, 장대 위는 매우 좁아서 교차할 수 없어 두 마리의 개미가 마주치면 반대 방향으로 돌아가야 합니다. 우리는 개미가 장대의 어디에 위치(Xi)하고 잇는지를 알 수 있습니다만, 불행히도 어느 쪽으로 향해 걷고 있는 지는 알 수 없습니다. 모든 개미가 자애로부터 떨어질 때까지 걸리는 최소시간과 최대시간을 각각 구하세요. 이라는 문제가 있었을 때, 재귀 함수로 전체 탐색을 하는 경우를 생각할 수 있다. 의 경우는 2^n으로 계산량이 증가한다. 더 나은 솔류션을 생각해보자. 가장 빠른 시간은 모든 개미가 가까운 장대 끝으로 향하는 것이다. 가장 느린 시간은 반대이면 된다...

이 문제에 오버타임에 대한 댓글이 있어서 데이터량이 큰 것을 알았다. 또한. 이 문제의 경우에는 테스트 케이스 수에 대한 정보도 없어서 테스트 케이스가 얼마나 많이 들어올지도 모른다는 것이다. 그래서 첫 번째로 생각한 솔류션은 list 배열에 각 인덱스에 대응하는 약수 개수를 저장해놓고 처음부터 각 값까지 max값을 계산해였다. 하지만, 이 경우, 문제 자체의 개수도 많았기에 5개뿐이 맞추지 못했다. 그래서 새로운 솔류션을 생각했다. list 배열에 차원을 하나 더 늘려 그 숫자까지의 max 값을 저장하는 것이었다. 그렇게 되면 처음 약수의 개수를 찾는 for문과 그 숫자까지의 max 값을 찾는 for문을 이용하여 값을 빠르게 찾을 수 있다. 시간복잡도는 100000(약수 개수 찾기)+100000(max..

아무리해도 논리가 맞아서 왜 안되지하다가 i가 j로 잘못적힌거 발견했다.... 다음부터는 이런 실수하지 않길... 먼저 순열을 받으면서 각 숫자에 대한 %3의 값을 저장하고 0번부터 자리값과 숫자값이 맞는 지 확인한다. 틀리다면, 그 이후로 swap해서 2개의 숫자가 제자리에 갈수 있도록하는 자리를 찾고, 없을 때를 대비하여 제자리에 있지 않고 현재자리의 값을 가지고 있는 숫자를 저장하여 swap한다. #include void swap(int list1[], int list2[]) { int temp[2] = { list1[0],list1[1] }; list1[0] = list2[0]; list1[1] = list2[1]; list2[0] = temp[0]; list2[1] = temp[1]; } int..

가장 큰 값과 가장 작은 값은 차이가 K이하여야 되고 그 안에 있는 다이아몬드는 모두 포함되어야 되기 때문에 정렬을 이용하는 것이 좋다. 정렬한 이후, 모든 값에서 모든 경우의 수를 생각해서 가장 max값을 선택하면 된다. 처음에는 처음과 끝에서부터 한칸이 줄여나가면서 풀면 가능할 것이라고 생각했는데 줄여나가는 기준을 찾지 못해서 새로운 방법으로 풀었다. #include # define MAX_SIZE 1010 int sorted[MAX_SIZE]; // 추가적인 공간이 필요 void merge(int list[], int left, int mid, int right) { int i, j, k, l; i = left; j = mid + 1; k = left; /* 분할 정렬된 list의 합병 */ whi..