Red Salmon

출처 : https://www.acmicpc.net/problem/2512

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2512.cpp

이 문제는 정보올림피아드 다운 문제였다. 어렵진 않지만 귀찮은 문제였다. 먼저 문제의 키포인트부터 보자.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

첫번째 조건을 살펴보면 즉 이런말이다. 입력으로 들어온 n을 다합쳐도 m으로 입력한 값보다 작거나 같으면 요청한 금액을 그대로 집행한다는 말이다. 

두번째 조건은 상한선을 둔다는 말인데, 요청한 금액이 적은녀석들은 그대로 두면서 높은 요청은 전부 동일한 상한선을 두어 나눠준다는 말이다.

읽자마자 나누기가 생각났다. 이유는 모르겠다.

나의 알고리즘은 다음과 같다.

1. 입력값을 먼저 정렬해준다.

2. 입력값의 총 합과 m을 비교후 m이 더크거나 같으면 정렬된 값의 맨 마지막을 출력한다.(문제는 가장 큰값을 출력하라고 했다.)

3. 그 외의 경우에는 요소 하나를 m에서 빼고 나머지 값을 현재 남은 요청수대로 나눠준다. 근데 이 값이 만약 현재 요청값보다 크다면 그 값을 채택한다. 

만약 요청값보다 작다면 버려지는 금액이 발생하기 때문에 더 배정할 수 있다는 말이 된다. 
(이런 생각을 왜 했냐고 물으면 나도 모른다. 생각이 났다.)

4. 하지만 m값에서 요청한 n을 나눈값이 만약 채택한 값보다 크다면 m에서 n을 나눈 값을 출력한다. 그게 아니라면 3번에서 채택한 값을 출력한다.

왜냐면 만약 요청값이 전부다 크고, m값이 작을때는 채택한 값보다 단순히 나눠준값이 더 클수도있다. 그렇기 때문에 이런 조건을 추가해줘야한다.  이걸 찾는데 상당한 시간을 허비했다. 보통의 경우는 이런식으로 나눠주면 모든 요소에 공통적으로 배분할수있도록 값이 나오는데 당연히 그값은 크지 않다. 

정보 올림피아드 문제는 풀때마다 생각하지만, 항상 까다롭고 귀찮은 예외 케이스가 존재한다. 이걸 한번에 생각하고 코딩하거나 그런 예외따위 무시하게만들면 최고의 알고리즘이지만 이처럼 예외가 발생하는 경우가 허다하다. 혼자 예제만드는 것또한 기술이라고 생각한다.

출처 : https://www.acmicpc.net/problem/2357

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2357.cpp

저번에 풀어본 최소값과 똑같은 문제이다. 다만 이번엔 최대값이 추가되었다. 알고리즘이 완전히 동일하기 때문에 생략한다.

약간의 팁아닌 팁을 적자면, 나는 함수의 인자로 vector<int> &tree라고 썼는데, 참조연산자를 빼버리고 vector<int> tree해도 정답은 나온다. 

차이는 메모리차이이다. 참조연산자를 주게되면 주소값이 계속 전달된다. 그러나 단순 tree만주면 재귀를 하는 과정에서 자꾸 복사를 하게 된다. 그러면 메모리를 더 사용하게 된다. 이는 알고리즘 문제풀때뿐만이 아니라, 실제 프로젝트를 진행함에 있어서도 주의를 해야한다.

자바로 하는 프로젝트의 경우 상관이 없겠지만, 타이젠처럼 C언어를 사용하거나, 안드로이드의 네이티비를 만들고 있
다면 이런점은 반드시 생각하며 코딩해야 한다. 메모리를 줄이는 것은 매우 중요한 일이다.

그리고 하나더 현재 입력이 10만인데, 10만번을 입력받으면 매우 느리다. 이럴때는 C++이라고 할지언정 cin, cout보다는 scanf와 printf를 사용해야 한다.

시간적으로 굉장히 큰 차이가 있다. 그리고 요번에 본 문서에는 endl의경우 버퍼를 자동적으로 비워준다고 하니 기억해둬야겠다.

출처 : https://www.acmicpc.net/problem/2632

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2632.cpp

이 문제는 좀 괜찮은 문제같다. 어렵지 않으면서 이것저것 생각할것도 조금 있고, 코딩도 상당히 해야한다.

문제를 살펴보면 피자의 크기의 최대는 2백만이고, 피자조각의 최대크기는 1000조각이다.

그럼 n^2(1000^2)까지는 계산이 허용된다는 말이니 여기에 중점을 두고 생각해보자.

그리고 주목해야할 부분이 바로 피자의 조각을 뺄때는 연속으로만 뽑을 수 있다고 한다.

그럼 각 피자당 뽑을수있는 경우의수는 매우 제한적이게 될 것이다. 

먼저 피자가 총 2조각으로 이루어져있다면 1조각짜리 2개 2조각짜리 1개로 구성되어 3개이다.

그리고 총 3조각이라면 1조각짜리 3개 2조각짜리 3개 3조각짜리 한개여서 총 5조각이다. 

수식으로 구해보면 n*(n-1)+1이 성립한다.

그럼 최대 인풋이 1000이니 식을 구해보면 대략 100만이 조금 안되는 값이 나온다. 그렇다면 배열에 모든 경우의수를 담아볼수있다.

피자는 2개로 구성되어있으니 총 2백만개의 배열이 필요하다.

그렇게 하여 각 피자당 구할수있는 모든 조각의 크기를 미리 구해놓는다. 그리고 한개의 피자에서 한개의 조각을 꺼냈을때 남은피자에서 n-사용한 조각을 하면 현재 필요한 조각수를 알수있으므로 그 조각수가 나오는 경우가 있는지 살펴보면 된다.

즉!! 이진탐색문제이다. 그러므로 당연히 정렬이 필요하다. 미리 구해둔 모든 조각의 크기를 정렬하고 구하고자 하는 값을 찾아보면 된다. 이때 중복이 있을수 있으니, 중복에 대한 경우를 체크하도록 한다.

그리고 하나더

시간단축을 위해 이진탐색에서 찾을 값이 음수이거나, 최대크기보다 큰값이라면 구할수 없으니 종료를 한다.

뿐만아니라 나는 나중에 깨달았지만 미리 idx배열을 1부터 시작한다면 즉 0인값을 넣어놓는다면 하단부분 계산파트에서 0인경우를 나처럼 따로 처리하지 않아도 된다. 그럼 코드가 더 간략해질것이다.

출처 : https://www.acmicpc.net/problem/1931

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1931.cpp

이 문제는 전형적인 그리드알고리즘이다. 그리고 아주 기초 그리드 알고리즘이다. 

먼저 입력을 종료값기준으로 정렬시킨다. 그리고 임시 변수에 종료값을 담아 두어, 계속 비교를 한다. 그런데 여기서 시작시간과 종료시간이 같을수도 있다고 하였으니 <= 식으로 표현해야 한다. 

그런식으로 표현을 하게 되면 종료시간이 제일 빠른 녀석을 처음에 고르게 되고, 그 종료시간으로부터 다음 시작을 하면서 종료시간이 제일 빠른녀석을 고르게 되므로 최대의 경우의수를 구할수있다.

n이 10만이기때문에 재귀로는 접근이 불가하고 이런식으로 풀어야한다.

그런데 여기서 재채점이 과거에 있었는데 나역시 정답이었다가 오답이되었다. (물론 지금은 다시 정답이다.)

요점은 이렇다.

1 1

1 2

2 2

2 3

이런식의 입력이 있을때 최대 선택이 몇개가 되야하는가다. 이건 x를 한번정렬을 해주면 된다. 그래서 있는것이 stable_sort인것이다. (참고 : http://www.cplusplus.com/reference/algorithm/stable_sort/)

x를 먼저 정렬해준수 stable_sort를 써서 y정렬을 해주면 깔끔하게 해결이 된다. 과거 stable_sort와 비슷하게 구현해봤는데 정말 귀찮았었던 기억이 있다. STL을 공부해두면 여러모로 편하다.