[PCCP] Lv4: 도둑질(42897)해설

문제

- 문제 링크: 도둑질

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: money의 길이

- dp 배열을 초기화할 때 시간 복잡도: O(N)

- 각 반복문을 수행할 때의 시간 복잡도: O(N)

- 최종 시간 복잡도: O(N)

public class Solution {
    public int solution(int[] money) {
        // 점화식에 필요한 변수를 초기화
        int n = money.length;
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        
        // 첫 번째 집을 도둑질하는 경우
        dp1[0] = money[0];
        dp1[1] = money[0];
        for (int i = 2; i < n - 1; ++i) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
        }
        
        // 첫 번째 집을 도둑질하지 않는 경우
        dp2[1] = money[1];
        for (int i = 2; i < n; ++i) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
        }
        
        // 두 경우 중 최댓값 찾기
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: money의 길이

- dp 배열 초기화: O(N)

- 각 반복문을 수행시 시간 복잡도: O(N)

- 최종 시간 복잡도: O(N)

def solution(money):
    # 점화식에 필요한 변수를 초기화
    n = len(money)
    dp1 = [0] * n
    dp2 = [0] * n
    
    # 첫 번째 집을 도둑질하는 경우
    dp1[0] = money[0]
    dp1[1] = money[0]
    for i in range(2, n - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
        
    # 첫 번쨰 집을 도둑질하지 않는 경우
    dp2[1] = money[1]
    for i in range(2, n):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])
        
    # 두 경우 중 최댓값 찾기
    answer = max(dp1[-2], dp2[-1])
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: money의 길이

- dp 배열을 초기화: O(N)

- 각 반복문 수행: O(N)

- 최종 시간 복잡도: O(N)

function solution(money) {
    // 점화식에 필요한 변수를 초기화
    const n = money.length;
    const dp1 = Array(n).fill(0);
    const dp2 = Array(n).fill(0);
    
    // 첫 번째 집을 도둑질하는 경우
    dp1[0] = money[0];
    dp1[1] = money[0];
    for (let i = 2; i < n - 1; ++i) {
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + money[i]);
    }
    
    // 첫 번째 집을 도둑질하지 않는 경우
    dp2[1] = money[1];
    for (let i = 2; i < n; ++i) {
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + money[i]);
    }
    
    // 두 경우 중 최댓값 찾기
    const answer = Math.max(dp1[n - 2], dp2[n - 1]);
    
    return answer;
}

solution 2)

import

solution 3)

import