글 읽기 - 문제 풀이에 대한 질문입니다..

wogus23 4년 전 0

일단 이렇게 풀긴했는데, 사실 고민 많이했습니다.이 풀이가 문제조건(N<=1000,제한시간2초)을 보고 가능하다고 생각은 했지만 음...뭐라할까요

생각없는코드?인것같아서..혹시 다른 정석풀이,신박한 풀이가 있으면 가르쳐 주시면 감사하겠습니다.정답률이 낮은데도 불구하고 이 문제에 대한 질문이 별로 없어서 정보 구하기가 힘드네요

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	int *arr = new int[N-1];
	int target;
	cin >> target;
	for (int i = 0; i < N-1; i++)
		cin >> arr[i];
	sort(arr, arr + N - 1);
	int count = 0;
	while (target <= arr[N - 2])
	{
		target++;
		arr[N - 2]--;
		sort(arr, arr + N - 1);
		count++;

	}
	cout << count;
}

richard0326 3년 전 0

일단 시간복잡도를 계산했을 경우, n이 최대 1000명, 득표수도 1000이기 때문에

다솜이가 0표이며 나머지가 999명이 모두 1000표를 갖고 있을 경우는 999번을 돌아야하고

while문의 반복 횟수는 최대 999이지만 1000으로 계산하면

sort는 merge sort임으로 nlogn이고

1000 x 1000 log(2) x 1000 = 300,000,000 이 됨으로 3초 걸리는 데. (1000 log(2) = 300)

실제로는 2초 안에 들어오네여....

제가 계산한게 맞나여?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 풀이에 대한 질문입니다..

wogus23 4년 전 0

richard0326 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말