Red Salmon

출처 : 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을 공부해두면 여러모로 편하다.

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

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

컨디션 난조로 적당히 할만한 문제를 잡았다. 이 문제의 경우 정보 올림피아드 출제 문제이다. 

나는 2가지 풀이법이 떠올랐다. 분명 더 훌륭한 알고리즘도 존재할거라고 생각한다.

우선 첫번째 알고리즘은 1000x1000배열을 생성한 후에 입력받은 값만큼 상자를 만들고, 왼쪽 맨아래를 0,0이라고 할때 x값을 증가시키면서 1을 발견하면 다시 위로 올가다가 끝이면 다시 오른쪽으로 가는 식으로 하여 1을 계속 채워나갈생각이었다. 최대 높 이에 도달하면 그 아래로 내려갈수가 없으니 끝까지가고 다시 맨뒤 막대부터 시작하려고 했다. 이렇게하면 정렬을 할 필요가 없는 장점이 있었다. 

암튼 이런 풀이를 하게 되면 문제에서 표기된 검은 라인이 생성될텐데, 이제 다시 검색을 시작하여 1과 1사이에 있는 모든 것들을 체크해주면서 카운팅을 해주면 정답이 나오겠구나~ 생각했다. 하지만 L과H가 10000이라면? 이건 풀수가 없게 된다. 왜냐면 배열값을 넘어버리기 때문이다.

그래서 두번째 방법을 생각했다.

결국 사각형의 넓이합이 아닌가? 선이 꺽이는 순간 2개의 x값의 차를 통해 밑변을 구하고 윗변 길이를 곱하여 sum을 계속 더해나가는 식으로 계산했다. 이게 훨씬 간단하고, 더 큰 크기에서도 잘 작동할것 같았다.

넓이의 최대값은 (1000x1000)이니까 백만이 최대가 되어 int로도 충분히 표현이 가능했다.

하지만 한번에 정답을 맞지는 않았는데, 놓치고 있는 부분이 있었다.

만약, 높이가 같다면?? 즉 나는 초기 풀이에 반드시 높이가 달라진다고 생각하였다. 하지만 혼자 테스트케이스를 만들어 테스트해보니 값이 맞지 않았다.

예)

5

1 11

2 11

3 11

4 11

5 11

이때 55가 나와야한다.

항상 소스를 간략화하고 줄이려다보니 나온 실수였다. 다음부턴 이런 실수를 하지 않도록 주의해야겠다.

소스 : https://github.com/stemp12/study/blob/master/Datastructure/single%20list.cpp

아흠 공부겸 오랜만에 리스트를 구현하였다. 여지껏 함수로만든 야매 리스트만 구현하다가 처음으로 객체지향적으로 구현해봤다. 물론 완벽하진 않을 것이며, 이보다 더 잘짠 코드는 널리고 널렸다. 

너무오랜만에 짜서그런지 오류고치고 하는데 너무많은 시간을 허비했다. 단일연결리스트경우는 10분이면 작성할수있어야 한다. 외우지는 않되 생각하지도 않고 짜는 수준이 되야하는데 아직은 생각하며 짜야하는 것이...연습이 더 필요할듯 하다.

이중 연결 리스트는 이 소스를 조금만 수정하면 되니, 다음에는 원형연결리스트를 구현해봐야겠다.

누군가가 이 소스로 공부를 하게 된다면 너무 심각하게 받아들이지말고 그냥 이런식이구나~ 정도만 참고하면 될것 같다.