[AC] 2304 창고 다각형

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

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