[백준/BOJ]9237. 이장님 초대 [Silver5]

9237. 이장님 초대

문제출처 : https://www.acmicpc.net/problem/9237

정말 오랜만에 백준 올리는거 같은데 꾸준히 안풀어서 그런가 잘안풀린다 ㅠㅠㅠ

code1

#include <stdio.h>
//insertion sort
void Sort(int list[], int n)
{
	int i, j, temp;
	for (i = 1; i < n; i++)
	{
		temp = list[i];
		for (j = i - 1; j >= 0 && list[j] <= temp; j--)
			list[j + 1] = list[j];
		list[j + 1] = temp;
	}
}
int main()
{
	int N, t[100000], temp, i, j, day = 1, big=0;
	scanf("%d", &N);
	temp = N;
	while (temp)
	{
		scanf("%d", &t[i]);
		i++;
		temp--;
	}
	Sort(t, N);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < i; j++)
		{
			if (t[j] > 0)
				t[j]--;
		}
		day++;
	}
	for (i = 0; i < N; i++)
		if (t[i] >= big)
			big = t[i];
	printf("%d", day+big);
	return 0;
}

처음짠거는 아니지만 어느정도 정리된 코드다.
비주얼 스튜디오에서는 오류없이 정상적으로 작동하는데, 백준에만 올리면 시간초과가 난다 ㅠㅠ

중간과정을 대폭 정리한 코드다.
어차피 결과는 나무를 모두심은데 걸리는 시간+ 나무가 다자라는데 걸리는 남은시간 + 1일 이기 때문에 그렇게 짯는데, 또 시간초과라면서 안되더라 ㅠㅠㅠㅠ
너무 오랜만에 복귀해서 감을 잃었나... 정렬도 헷갈리고 하더라 저번 2주동안 14일중 8일을 수업나가서 너무 정신이 없었다 ㅠㅠ 다시 일상으로 돌아왔고, 휴가도 짧게 다녀왔으니 다시 힘내서 해보겠다

code2

#include <stdio.h>
void Sort(int list[], int n)
{
	int i, j, temp;
	for (i = 1; i < n; i++)
	{
		temp = list[i];
		for (j = i - 1; j >= 0 && list[j] <= temp; j--)
			list[j + 1] = list[j];
		list[j + 1] = temp;
	}
}
int main()
{
	int N, t[100000], temp, i=0,big=0;
	scanf("%d", &N);
	temp = N;
	while (temp)
	{
		scanf("%d", &t[i]);
		i++;
		temp--;
	}
	Sort(t, N);
	for (i = 0; i < N; i++)
		t[i] -= N - 1 - i;
	for (i = 0; i < N; i++)
		if (t[i] >= big)
			big = t[i];
	printf("%d", big + N + 1);
	return 0;
}

8/24 추가 블로그이사하면서 보니까 버블정렬, 삽입정렬만 쓴것 같은데 퀵소트를 쓰면 시간초과 문제가 풀리지않을까 생각한다. 내일이나 시간남을때 퀵소트로 바꿔서 한번 제출해봐야겠다.
진짜 저때 스케줄너무많아서 개스트레스받았는데;;;

예상대로 퀵소트로 푸니까 됐다.

code

#include <stdio.h>
void QuickSort(int arr[], int start, int end)
{
	if (start >= end)
		return;
	int piv = start;
	int left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[piv])
			left++;
		while (right > start && arr[right] <= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, t[100000] = {0}, temp, i = 0, big = 0;
	scanf("%d", &N);
	temp = N;
	while (temp)
	{
		scanf("%d", &t[i]);
		i++;
		temp--;
	}
	QuickSort(t,0, N-1);
	for (i = 0; i < N; i++)
		t[i] -= N - 1 - i;
	for (i = 0; i < N; i++)
		if (t[i] >= big)
			big = t[i];
	printf("%d", big + N+1);
	return 0;
}