[Programmers] 쿠키 구입

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/49995

코딩테스트 연습 - 쿠키 구입

이분 탐색과 DP를 이용하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 우선 전처리를 통해 구간합을 미리 다 구해줍니다. ex) cache[i][j] = [i, j] 구간의 합

2. [l ~ m] 구간합과 동일한 [m + 1 ~ r] 구간 합을 구해주기 위해 아래와 같이 이분 탐색을 진행해줍니다.

2.1 left를 m + 1, right를 cookie 배열의 크기로 잡아주고 이분 탐색을 진행해주는데 [m + 1 ~ mid] 구간합이 [l~m] 구간합보다 작으면 구간을 넓혀주고 크면 구간을 좁혀줍니다.

2.2 정확한 [m + 1 ~ r] 구간을 찾았으면 answer를 업데이트 해주고 이분 탐색을 멈춰줍니다.

3. 2번을 통해 얻은 값을 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~