[PCCP] Lv2: 땅따먹기(12913) 해설

문제

- 문제 링크: 땅따먹기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

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: 행의 길이

- 반복문은 총 4*N번 실행하므로 최종 시간 복잡도는 O(N)

import java.util.Arrays;

class Solution {
    int solution(int[][] land) {
        // 각 행마다 이전 행에서의 최대 점수를 더해가며 최대 점수를 구함
        for (int i = 1; i < land.length; ++i) {
            for (int j = 0; j < 4; ++j) {
                // 이전 행에서 현재 열의 값을 제외한 나머지 열들 중에서 가장 큰 값을 더함
                int max = 0;
                for (int k = 0; k < 4; ++k) {
                    if (j != k)
                        max = Math.max(max, land[i - 1][k]);
                }
                land[i][j] += max;
            }
        }
        // 마지막 행의 값 중에서 최댓값 반환
        return Arrays.stream(land[land.length - 1]).max().getAsInt();
    }
}

solution 2)

import java.util.*;
class Solution {  
   public int solution(int[][] land) {
       for(int i=1; i<land.length; i++){
           land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);
           land[i][1] += Math.max(Math.max(land[i-1][0], land[i-1][2]), land[i-1][3]);
           land[i][2] += Math.max(Math.max(land[i-1][1], land[i-1][0]), land[i-1][3]);
           land[i][3] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][0]);
       }

       int[] answer = land[land.length-1];
       Arrays.sort(answer);

       return answer[answer.length-1];
   }
}

solution 3)

#include<>

 

(Python)

solution 1)

- N: 행의 길이

- 반복문은 4*N번 실행

- 총 시간 복잡도: O(N)

def solution(land):
    # 각 행마다 이전 행에서의 최대 점수를 더해가며 최대 점수를 구함
    for i in range(1, len(land)):
        for j in range(4):
            # 이전 행에서 현재 열의 값을 제외한 나머지 열들 중에서 가장 큰 값을 더함
            land[i][j] += max(land[i - 1][:j] + land[i - 1][j + 1:])
    
    # 마지막 행에서 얻을 수 있는 최대 점수를 반환
    return max(land[-1])

solution 2)

def solution(land):

    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])

    return max(land[len(land)-1])

solution 3)

import

 

(JavaScript)

solution 1)

- N: 행의 길이

- 반복문은 4*N 번 실행: O(N)

function solution(land) {
    // 각 행마다 이전 행에서의 최대 점수를 더해가며 최대 점수를 구함
    for (let i = 1; i < land.length; ++i) {
        for (let j = 0; j < 4; ++j) {
            // 이전 행에서 현재 열의 값을 제외한 나머지 열들 중에서 가장 큰 값을 더함
            land[i][j] += Math.max(...land[i - 1].filter((_, index) => index !== j));
        }
    }
    
    // 마지막 행에서 얻을 수 있는 최대 점수를 반환
    return Math.max(...land[land.length - 1]);
}

solution 2)

function solution(land) {
    return Math.max(...land.reduce((target, score) => {
        return [
            score[0] + Math.max(target[1], target[2], target[3]),  
            score[1] + Math.max(target[0], target[2], target[3]),
            score[2] + Math.max(target[0], target[1], target[3]),
            score[3] + Math.max(target[0], target[1], target[2]),
        ];
    }, [0, 0, 0, 0]));
}

solution 3)

import