Red Salmon

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

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

음..이문제는 정말 어렵게 풀었다. 사실 풀지 못하였고 다른사람의 코드를 보고 다시작성하였다. 그게 약 9개월 전이고 이번에 복습겸 다시 풀었다.

먼저 문제는 여러 직사각형의 전체 면적을 구하라고 하는데 입력이 소수이다. 배열에 다 때려박고 계산하는식의 계산을 할 수 없다. 이런걸  brute force라고 하는데 이건 알고리즘이 아니다. 

이 문제의 경우 이런식으로 생각하면 이해가 쉽다. 

이런식으로 도형이 나열되어 있다고 생각해보자. 전체 넓이이니 도형들을 세분화시켜서 그 합을 구해도 값은 같을 것이다.

즉 이런식으로 나누게 된다. 

필자는 귀찮아서 선을 전부 그리지 않았다. 더그려야한다. 대략적인 느낌만 알면 된다. 암튼 모든 점에 대하여 선을 나누면 무수히 많은 사각형이 나온다. 이 사각형들 중에 입력으로 들어온 사각형과 비교하여 포함이 된다면 그 값을 계속 더해주면 된다.

이 알고리즘의 경우 O(n^3) 이 되므로  n값이 크다면 역시 올바른 알고리즘이 되지 못한다. 그래서 과거 검색해보니 인덱스트리나 다른 알고리즘을 사용하면 O(lgn) 까지도 줄어든다고 한다. 그런데 너무 복잡하고 어려워서 포기했던 기억이 있다. 

그러나 이 문제를 풀기에는 n^3도 무방하니 이 알고리즘을 사용해도 되겠다. 그리고 범위를 찾는데 다음과 같이

bool chk(double x1, double x2, double y1, double y2, Rect rect)
{
    //return rect.x1x1 && rect.y1y1;
    return rect.x1<=x1 && rect.x2>=x2 && rect.y1<=y1 && rect.y2>=y2;
}
// 두가지 방법이 있다.

위 에 두가지 방법이 있는데 둘중 아무거나 써도 된다. 대부분의 코드를 보니 상단의 방법을 많이쓰고 과거 트리문제를 풀었을때도 저런 비교를 많이 한다. 하단의 방법도 맞으나, 가급적이면 상단의 방법을 쓰면서 이해하는게 응용하기 훨씬 쉬울거 같다.

출처 : 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/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/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가 나와야한다.

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