프로그래머스 - 쿠키 구입(feat. Java)

문제 정보는 아래 링크를 확인해주세요!

 

[쿠키 구입]

프로그래머스

 

문제 접근 방법

• 쿠키 바구니를 나눠주는 방법은 쿠키 배열의 연속된 값들을 왼쪽/오른쪽으로 구간을 나눠서 비교하는 것과 같다
• 쿠키 배열의 왼쪽 첫 번째 요소부터 마지막-1번째 요소까지 dfs 탐색
• DFS 탐색 시작
• DFS 탐색은 첫 번째 요소와 두 번째 요소의 비교로 시작하면서 파라미터로 왼쪽/오른쪽 합계와 각각의 인덱스를 담는다
• 왼쪽 요소의 인덱스를 하나씩 줄여가며 구간합을 구하는 DFS
• 오른쪽 요소의 인덱스를 하나씩 늘려가며 구간합을 구하는 DFS
• 왼쪽 요소와 오른쪽 요소가 같다면 최댓값과 비교

[소스 코드]

package algorithm.programmers;

/*
 * 2018 summer/winter conding
 * 쿠키 구입
 * */
public class Pro49995 {
    private static int max,len;
    private static int[] COOKIE;

    public static int solution(int[] cookie) {
        int answer = 0;

        COOKIE = cookie;

        max = 0;
        len = cookie.length;

        for (int i = 0; i < len-1; i++) {//첫 번째부터 마지막-1 요소까지 dfs 탐색
            dfs(COOKIE[i],COOKIE[i+1],i,i+1);
        }
        answer = max;
        return answer;
    }

    private static void dfs(int A,int B, int cnta, int cntb) {

        if (A == B) {//같으면 최댓값과 비교
            max = Math.max(max, A);
        }

        if (cnta > 0 && A <= B) {//왼쪽 구간을 늘리는 방식으로 DFS 탐색
            dfs(A+COOKIE[cnta-1],B,cnta-1,cntb);//cnta를 줄이는 이유는 처음 for문과 관계가 있다.
        } else if (cntb < len-1 && A >= B) {//오른쪽 구간을 늘리는 방식으로 DFS 탐색
            dfs(A,B+COOKIE[cntb+1],cnta,cntb+1);
        }

    }
}