2019 JOIOC+2019 봄통교 5주차(멘토교육 4주차)

문제를 1시간 동안 보고 느낀 생각과 문제 요약:

1번: a<b<c, b-a<=c-b일 때 A_a+A_b+A_c의 최댓값을 구하는데, L<=a,c<=R이여야 하는 조건이 추가되는 쿼리가 N개 주어집니다. 보자마자 고난도의 자료구조 문제일 가능성이 높다고 생각했고, 다른 문제를 보러 갔습니다.

2번: 원형 배열이 있는데, 어떤 원소에서 2a를 빼고 다음 원소에 a를 넣는 작업을 반복하여(a는 정수, 배열의 원소는 항상 0 이상이여야 함) 원형 배열을 주어진 배열로 바꿔야 하는 문제입니다. 원소 i에서 원소 i+1로 주는 연산들의 a의 합을 C_i라고 하면, C_i-1-2C_i=초깃값-목푯값이여야 합니다. 이를 수식으로 정리하면 C_i=2^N*C_i+2^N-1(i-1번째 원소 초깃값-i-1번째 원소의 목푯값)+2^N-2(i-2번째 원소의 초깃값-i-2번째 원소의 목표값).....+2*(i+1번째 원소 초깃값-i+1번째 원소 목푯값)+(i번째 원소 초깃값-i번째 원소 목푯값)이 나오고, i-1,i-2,....i-100번째 정도까지만 신경써주면 1~2 차이 내로 비슷한 값이 나오므로 주변 몇 개를 시도해보고, 모든 C_i가 양수인지 확인하면 된다고 생각했습니다.

3번:N<=2500개의 점이 있는 좌표평면에서 우리가 알지 못하는 점 하나가 N개의 점들을 꼭짓점으로 하는 볼록다각형 안에 있는지 물어보는 쿼리를 최대 40번 해서 우리가 알지 못하는 점이 있다고 확신할 수 있으면서 내부에 다른 점이 없는 볼록다각형을 구하는 문제입니다. 로그 정도 개수의 쿼리, Yes,No 답변 등을 통해서 볼록 껍질을 구한 뒤 그 안에서 이분 탐색을 하는 것을 반복하는 것 같다는 생각이 들었습니다.

1시간 동안 생각하고 난 뒤에는 위에 있는 2번 풀이를 구현했습니다. 제가 빼먹은 케이스가 하나 있어서 WA가 나왔습니다. 모든 목푯값이 0인 경우가 반례인 것을 10분 정도의 테스팅 뒤에 확인하고, 예외처리를 해서 AC를 맞았습니다.

그 다음에는 3번을 더 생각했습니다. 제 3번 풀이의 기본 틀은 다각형의 컨벡스 헐을 구한 뒤 컨벡스 헐에 없는 한 점을 골라서 이 점과 컨벡스 헐에 있는 모든 점을 연결하는 선을 그어 컨벡스 헐을 삼각형으로 나누고, 이분 탐색으로 어떤 삼각형에 있는지 구한 뒤 반복하려 했습니다다. 하지만 시간은 2시간도 정도 남았고, 구현을 시간 안에 마칠 수 있는지 확신이 없었습니다. 그래서 삼각형으로 나누는 대신 4개의 볼록 다각형으로 나누고, 이분 탐색을 생략하도록 풀이를 바꿨고, 구현을 시작했습니다. 기하 문제이다 보니 구현 시간은 오래 걸렸고, 디버깅을 시작할 때 시간은 1시간 미만으로 남아 있었습니다. 디버깅 중 60점이라도 받기 위해, 4개의 볼록 다각형으로 나누는 부분을 지웠고, 원래대로 삼각형으로 나눴더니 0점에서 60점으로 올랐습니다. 그 뒤 4개의 볼록 다각형으로 나누는 부분을 다시 짜 만점을 맞을 수 있었습니다.

3번을 풀고 시간은 20분 정도 남았었는데, 그 동안 1번을 긁었습니다. 시작이 a, 끝이 c로 고정되어 있는 거는 c를 증가시켜가며 쉽게 찾을 수 있었고, 이를 dp를 사용해서 시작이 a 이상, 끝이 c 이하인 것을 구하도록 했습니다. 20분 동안 총 19점을 긁을 수 있었습니다.

저번과는 다르게 이번에는 풀 수 있는 문제들을 시간에 맞게 풀 수 있었고, 아이디어도 생각이 잘 났던 것 같습니다. 특히 2번은 백준에서 찾아보니 다이아 4였는데 그리 어렵지 않게 생각을 할 수 있어서 좋았습니다.