MingyuPark

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어1 - DP Pypy3에서는 성공했고, Python에서는 시간 초과가 발생한 방법이다. 아이디어는 다음과 같다. 자연수 n에 대하여, n을 최소 개수의 제곱수 합으로 표현했을 때 그 개수를 f(n)이라고 하자. 이 때, n보다 작은 모든 제곱수 k에 대해 m = n - k 라고 하면, f(n)은 f(m)의 최솟값 + 1이 된다. (제곱수를 더한다는 ..

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아이디어 그리디 알고리즘으로 접근할 수 있다. 그 근거를 살펴보자. 지금 시점에 시작할 수 있는 회의들 중에서 가장 빨리 끝나는 회의를 진행하면 된다. 시작 시간을 고려하면 안된다. 시작 시간 자체는 다음 회의를 탐색하는 데에 있어서 기준이 될 수 없다. 이번 회의가 일찍 끝나면 끝날수록 더 많은 다음 회의를 고려할 수 있다. 결론은, 일단 모르겠고 제일 먼저 끝나는 걸 찾자. 이다. 예를 들어보자. 회의 시간이 (1, 4), (2, 3), (3, 5) 라고 하자. 시작 시간 기준으로 정렬하면 (1, 4) ..