Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1620.cpp

문자열 + 이진탐색 문제이다. 어려울건 없었다. 그냥 따로 분리를 하여 숫자용 하나 문자용 하나 두고 검색하여 정답을 출력하면 된다. 딱히 고민했던 에러사항도 없다.

다만 입력이 10만번에 출력도 그만큼이다. 즉 cin은 안되는데 대충보고 그냥 했다가 시간초과가 났다.

이 부분만 고쳐주면 된다. 

그리고 string형식은 그냥 <, > 으로 비교가 가능하지만  char * 형식은 저런 비교가 되지 않으니 반드시 strcmp를 써야 한다. 물론 string형식도 compare함수가 존재하지만 <, >로도 원하는 결과를 얻을수 있다.

마찬가지로 string은 =로 값을 대입할수있으나 char * 는 불가하므로  strcpy를 사용해야 한다.

참으로 C++은 편리한 것이다.  또한 이런정도 함수들은 알고 있어야 문제풀기 수월할 것이다.

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

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2805.cpp

이 문제는 이진탐색 문제이다. 문제를 딱보니 DP아니면 이진탐색의 느낌이 강했고, 더 살펴보니 이진탐색 문제였다.

DP 문제가 아니라는건 뭔가 감이었다. 예전에는 이런 구분이 잘 안되었는데 이젠 그냥 뭔가 보인다.

 문제는 어떤 기점으로 잘랐을때 요구한 길이에 가장 근접하게 자르라는 말이다.  예전에 황소 울타리문제? 그거랑 비슷한거 같다.

접근은 다음과 같다.

1. 정렬한다.

2. 먼저 입력값을 통해 대강적인 위치를 찾는다. (지금 생각해보니 굳이 찾을 필요가 없다.) 대강적인 위치는 입력배열의 인덱스이다.

3. 해당 인덱스를 통해 left right값을 구하면 이제 값은 arr[left]<=정답<=arr[right] 인것이기 때문에 범위가 상당히 좁아졌다. 여기서부터는 인덱스가 아닌 값으로써 다시 검색을 한다.

4. 일치되는 값이 있으면 그 값을 리턴하고 없다면 middle을 가지고 다시 state함수를 호출하여 middle을 그대로 사용할지 아니면 -1을 해줘야할지 판별한다. 

이 문제를 풀면서 조금 졸렸고, 코드가 길어져 짜증나 계속 줄이려고했는데 생각해보니 몇몇의 개선점이 보인다.

1. state함수는 계속 합을 구하는 함수인데, 좀 더 생각해보면 처음 이진탐색이후 3번과정을 할때는 이미 arr[right]로 값이 변경된 시점에서 right는 고정이 되었으므로 한번에 합을 구하고 그 후부터는 인덱스가 변할때 그 차만큼 +1 혹은 -1을 해주면 되지 않았을까 싶다. 그러면 굳이 처음부터 끝까지 합을 구하는 과정이 많이 생략되었을거 같다. 뭐 어차피 로그시간대라서 그냥 무시하고 진행하였다...

2. 나는 이진탐색을 둘로 나누었는데 지금 생각하니 굳이 그럴 필요가 없는것 같다. 하나만두고 처음부터 값을 통해 찾았다면 더 나은 코드가 되지 않았을까 생각이 든다. 역시 졸릴땐 문제를 풀면 안되는것 같다. 코드가 더 간략해지고 깔끔해질수있었을텐데 하는 아쉬움이 남는다.

출처 : 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인경우를 나처럼 따로 처리하지 않아도 된다. 그럼 코드가 더 간략해질것이다.