프로그래머스 땅따먹기(lv2) 풀어보기

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

---

문제 핵심

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.

---

알고리즘

-두줄씩 같은 열제외하고 더함

해당 행에 열끼리 더한값을 묶음

해당 좌표의 최고합만 구함

그리고 최고가를 매번 갱신함

---

코드

 static int solution(int[][] land) {

        int answer = 0;

        int index = 0;

        int[] maxs = new int[land[0].length];

        boolean first = true;

        while (index < land.length - 1) {

            Map<Integer, Integer> tempMaxs = new LinkedHashMap<>();

            for (int i = 0; i < land[0].length; i++) {

                for (int ii = 0; ii < land[0].length; ii++) {

                    if (i == ii) {

                        continue;

                    }

                    int nmax = 0;

                    if (first) {

                        System.out.print(" 처음임");

                        System.out.println("연산예정: " + land[index][i] + " + " + land[index + 1][ii]);

                        nmax = land[index][i] + land[index + 1][ii];

                        if (tempMaxs.containsKey(ii)) {

                            if (tempMaxs.get(ii) < nmax) {

                                tempMaxs.put(ii, nmax);

                            }

                        } else {

                            tempMaxs.put(ii, nmax);

                        }

                    } else {

                        System.out.println("연산예정: " + maxs[i] + " + " + land[index + 1][ii]);

                        nmax = maxs[i] + land[index + 1][ii];

                        if (tempMaxs.containsKey(ii)) {

                            if (tempMaxs.get(ii) < nmax) {

                                tempMaxs.put(ii, nmax);

                            }

                        } else {

                            tempMaxs.put(ii, nmax);

                        }

                    }

                }

            }

            System.out.println("최고값후보현황: " + tempMaxs);

            for (Map.Entry<Integer, Integer> entry : tempMaxs.entrySet()) {

                int idex = entry.getKey();

                int max = entry.getValue();

                if (maxs[idex] < max) {

                    maxs[idex] = max;

                }

                if (answer < max) {

                    answer = max;

                }

            }

            tempMaxs.clear();

            System.out.println("최고값현황: " + Arrays.toString(maxs));

            first = false;

            index += 1;

        }

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

알고리즘

알고리즘은 적절해. 핵심을 제대로 잡았어.

코드에서 가장 크게 개선할 부분

지금은 Map도 사실 필요 없어.

Map<Integer, Integer> tempMaxs = new LinkedHashMap<>();

key가 무조건 0,1,2,3이잖아. 그러면 그냥:

int[] tempMaxs = new int[land[0].length];

이면 돼.

그러면 이 코드:

if (tempMaxs.containsKey(ii)) {
    if (tempMaxs.get(ii) < nmax) {
        tempMaxs.put(ii, nmax);
    }
} else {
    tempMaxs.put(ii, nmax);
}

가 그냥:

tempMaxs[ii] = Math.max(tempMaxs[ii], nmax);

한 줄이 돼.

first도 없앨 수 있음

지금 first가 필요한 이유는 최초에 maxs가:

[0, 0, 0, 0]

이기 때문이잖아.

처음부터:

int[] maxs = land[0].clone();

하면:

[1, 2, 3, 5]

로 시작할 수 있어.

 

 

 

---

후기

-2틀동안 고민했다

1차시도 그냥 dfs로 구현-시간초과

gpt조언 모든 경우의 수를 돌필요없다 왜?

어차피 해당수에 도착한 수들은 다음 과정은 똑같다

조언을 듣고 다시 생각해봤다

 

어 결국 그러면 해당 경로의 최고값들로만 했으면 되는구나 하고

구현 하고 통과했다 아 어려웠다.