프로그래머스 문제풀이 (알고리즘) - 도둑질

문제

https://programmers.co.kr/learn/courses/30/lessons/42897#

코딩테스트 연습 - 도둑질

 

시도 3 (정답)

이 집을 털 수 있는 경우와 이 집을 털 수 없는 경우 중에서
더 많은 금액을 보유할 수 있는 경우를 선택해야 하는 문제로 생각

만약 i 번 집에 도착했을 때 가지고 있는 최대 금액을 dp[i] 라고 하면, 다음과 같이 2경우가 생긴다
* 이 집을 털 수 있는 경우 
	=>  이전 집을 털지 않은 것. 최대 금액을 훔쳐야 하기 때문에 이 집은 턴다. 
		  dp[i] = dp[i-2] + money[i] 
		  2번 째 전 집에서 가지고 있던 최대 금액에 현재 금액을 더한 것

* 이 집을 털 수 없는 경우
	=>  이전 집을 턴 것 dp[i] = dp[i-1] 
	    즉, 이전 집에 도착했을 때 가지고 있는 최대 금액을 이번 집에서도 그대로 가지고 있어야 합니다.

위 두 경우 중에서 최대로 많은 금액을 털 수 있는 경우를 선택합니다.

단, 첫 시작은 어떻게 할 것인지 결정해야 하는데 다음과 같은 2경우가 있습니다.
* 0번째 집을 털고 시작하는 경우 => 마지막 집은 털 수 없습니다
* 0번째 집을 털지 않고 시작하는 경우 => 1번째 집을 무조건 텁니다

이전까지의 탐색 결과를 배열에 가지고 있음으로써 연산 회수를 줄입니다.

public int solution(int[] money) {

    int[] dp0 = new int[money.length];
    int[] dp1 = new int[money.length];

    // 첫 번째 케이스
    dp0[0] = money[0];
    dp0[1] = money[0];

    // 두 번째 케이스
    dp1[0] = 0;
    dp1[1] = money[1];

    // 1번 째 케이스, 돈을 쭉 텁니다.
    for (int i = 2; i < money.length; i++) {
        // 마지막 집은 털 수 없음
        if (i == money.length - 1) {
            dp0[i] = dp0[dp0.length - 2];
            break;
        }

        dp0[i] = Math.max(dp0[i - 1], dp0[i - 2] + money[i]);
    }

    // 2번 째 케이스, 돈을 쭉 텁니다.
    for (int i = 2; i < money.length; i++) {
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
    }

		// 최대 값 반환
    return Math.max(dp0[dp0.length - 1], dp1[dp1.length - 1]);
}

 

시도 1 (오답)

가장 간단하게 생각할 수 있는 방법으로 풀어보기로 함

단순히 한집 건너 한집을 터는 방법

public int solution(int[] money) {
    int one = 0;
    int two = 0;

    for (int i = 0; i < money.length; i++) {
        if (i % 2 == 0)
            one += money[i];
        else
            two += money[i];
    }

    return Math.max(one, two);
}

당연히 실패

이렇게 되면 {10, 1, 2, 11, 1} 으로 집이 나열 된 경우 10 + 11 의 금액을 털어야 가장 큰 금액을 털 수 있는데 10 + 2 + 1 또는 1 + 11 의 경우로 밖에 털 수 없음

 

시도 2 (오답)

깊이 우선 탐색을 이용해보기로 함

가장 쉽게 생각할 수 있는 방법은 재귀호출을 이용한 깊이 우선 탐색

// 탐색을 모두 마친 후, total 값 중 최대 값을 구하기 위해 멤버 필드 하나 생성
private int max = Integer.MIN_VALUE;

/**
 * 재귀 호출을 이용한 깊이 우선 탐색
 */
public void dfs(int search, int[] isVisit, int[] money) {

    // 마지막까지 탐색을 마친 경우
    if (search >= isVisit.length) {
        int total = 0;
        for (int i = 0; i < isVisit.length; i++)
            if (isVisit[i] == 1)
                total += money[i];

        if (max < total)
            max = total;
        return;
    }


    // search 보다 최소 2 이상 큰 수를 탐색. 최대 2를 더 넘는 수 까지는 탐색
    for (int i = search + 2; i < isVisit.length + 2; i++) {
        // 탐색
        isVisit[search] = 1;
        dfs(i, isVisit, money);
        isVisit[search] = 0;
    }
}


public int solution(int[] money) {
    int[] isVisit = new int[money.length];

    dfs(0, isVisit, money);
    dfs(1, isVisit, money);

    return max;
}

이 방법은 모두 시간 초과 or 메모리 초과로 실패했다.

일단 풀이 방법 자체가 틀린 것은 아닌 것 처럼 보인다.

왜냐면 모든 경우를 전부 검사하는 로직이기 때문이다.

그런데 에초에 문제 주제가 동적 계획법이었으니, 이 방법이 성공할 것 같지는 않았다.

동적 계획법이라함은 문제를 쪼개서 풀어냄으로서 연산 회수를 기하 급수적으로 줄일 수 있는 방법인데,

보통 계산한 값을 버리지 않고 가지고 있음으로서 했던 연산을 또하고 또하는 것을 방지하는 방식이다.

그래서 메모리 초과로 틀릴 것이라고 예상했던 바였다.

 

시도 2 - 1 (오답)

(물론 이 방법은 오답이다.)

동적 계획법으로 풀어야 하니까 4개씩 쪼개서 계산하면 되지 않을까? 하는 생각에서 아래와 같은 풀이를 작성했다.

그런데 이것은 정말 멍청한 생각이었다.

이러면 한집을 털었을 때 바로 옆집을 털 수 없다"는 규칙을 어기게 되기 때문이다.

단, 메모리 문제나 시간 문제로 틀리던 전과 다르게 속도 자체는 확연하게 빨라졌다.

// 탐색을 모두 마친 후, total 값 중 최대 값을 구하기 위해 멤버 필드 하나 생성
private int max = Integer.MIN_VALUE;

/**
 * 재귀 호출을 이용한 깊이 우선 탐색
 */
public void dfs(int search, int[] isVisit, int[] money) {

    // 마지막까지 탐색을 마친 경우
    if (search >= isVisit.length) {
        int total = 0;
        for (int i = 0; i < isVisit.length; i++)
            if (isVisit[i] == 1)
                total += money[i];

        if (max < total)
            max = total;
        return;
    }


    // search 보다 최소 2 이상 큰 수를 탐색. 최대 2를 더 넘는 수 까지는 탐색
    for (int i = search + 2; i < isVisit.length + 2; i++) {
        // 탐색
        isVisit[search] = 1;
        dfs(i, isVisit, money);
        isVisit[search] = 0;
    }
}



public int solution(int[] money) {

    int result = 0;
    int i = 0;

    for (i = 0; i < money.length; i += 50) {
        if (money.length > 50) {
            int[] copy = Arrays.copyOfRange(money, i, i + 50);
            int[] isVisit = new int[copy.length];

            dfs(0, isVisit, copy);
            dfs(1, isVisit, copy);
            result += max;
            max = Integer.MIN_VALUE;
        } else {
            int[] copy = Arrays.copyOfRange(money, i, money.length);
            int[] isVisit = new int[copy.length];

            dfs(0, isVisit, copy);
            dfs(1, isVisit, copy);
            result += max;
            max = Integer.MIN_VALUE;
        }
    }

    // i 가
    if (i < money.length) {
        int[] copy = Arrays.copyOfRange(money, i - 50, money.length);
        int[] isVisit = new int[copy.length];

        dfs(0, isVisit, copy);
        dfs(1, isVisit, copy);
        result += max;
    }


    return result;
}