[백준 2579번] 계단 오르기

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

계단마다 점수가 매겨져있고, 각 계단을 1칸 또는 2칸씩 뛰어 오를 수 있다.

but 한번에 3계단을 연속해서 밟을 수 없을 때 얻을 수 있는 총 점수의 최댓값을 구하는 문제

 

계단의 갯수인 N은 N<=300인 자연수이고, 

각 계단의 점수는 10,000이하인 자연수이다.

 

2. 나의 방식대로 문제를 재정의 하자.

n번째 계단까지 올라갈 때의 최대값을 memory에 저장하여 출력한다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

반복문과 재귀함수를 사용

n번째 계단의 최댓값 += max((n-1계단의 최댓값), (n-2 계단의 최댓값))

단 연속으로 3번 계단을 밟을 수 없으므로 깊이를 저장하는 변수를 활용한다.

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader 이용

 

2) 시간 복잡도 계산

O(n)

 

5. 주의할 점은 무엇인가?

연속해서 3계단을 밟으면 안된다는점에 주의해야함

 

 

6. 풀이 과정

1) 재귀함수

import java.io.*;

public class q2579 {
    static int[][] memory;
    static int[] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Integer N = Integer.parseInt(br.readLine());
        memory = new int[N][2];
        cost = new int[N];

        for (int i = 0; i < N; i++) {
            cost[i] = Integer.parseInt(br.readLine());
        }
        

        bw.write(calc(N - 1, 0) + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int calc(int n, int depth) {
        if (n == 0 || (n == 1 && depth == 1)) {
            memory[n][depth] = cost[n];
            return memory[n][depth];
        }

        if (memory[n][depth] != 0) {
            return memory[n][depth];
        }

        if (depth == 1) {
            memory[n][depth] = calc(n - 2, 0) + cost[n];
        } else if (n == 1) {
            memory[n][depth] = calc(n - 1, 1) + cost[n];
        } else {
            memory[n][depth] = Math.max(calc(n - 1, 1), calc(n - 2, 0)) + cost[n];
        }
        

        return memory[n][depth];
    }

}

 

재귀문을 돌면서 두번째로 연속한 계단을 밟을 때 depth에 1을 줘서 다음 계단은 2칸 띄어 들어가도록 했다.

0. 함수 정의 : int calc(int n, int depth);

1. 함수의 기능 : n번째 계단을 (depth+1)번째로 연속된 순서로 밟을 때 가지는 최대값 

2. 반환조건

 - n = 0일경우

       첫번째 계단이므로 depth와 관계 없이 해당 계단의 점수를 리턴한다.

 - n == 1 && depth == 1일 경우

       두번째 계단이고 두번째로 연속되는 계단이므로, 첫번째 계단을 밟지 않고 해당 계단의 점수를 리턴한다.

 - memory[n][depth]의 값이 이미 있을 경우

       이미 계산한 값이므로 계산되어져 있는 값 리턴

3. 함수 내부 로직

 3-1) depth ==1 일 경우

  더이상 연속한 계단을 밟지 못하므로 (n-2번째 계단을 밟았을 때의 점수) + (현재 계단 점수) 연산을 한다.

 3-2) n ==1 일 경우

  두칸 건넌 계단이 존재하지 않으므로 (n-1번째 계단을 밟았을 때의 점수) + (현재 계단 점수) 연산을 한다.

 3-3) 그외

  (n-2번째 계단을 밟았을 때의 점수) 와  (n-1번째 계단을 밟았을 때의 점수) 중 더 큰 값과 (현재 계단 점수)를 더하기 연산 한다.

 

 

처음에 문제를 접근할 때 memory에 저장하는 값을 depth와 상관없이 저장하게 짜는 바람에 계속 오류가 생겼다.

오류가 생긴 부분은 재귀문이 돌면서 2번째 계단에서 depth가 1일경우 1번째 계단을 밟지 않으므로 자기자신 값만 저장하는데, 나중에 다시 재귀를 돌면서 memory[2]의 값이 필요해졌는데  그때의 depth가 0일 경우에는 첫번째 계단을 더하지 않은 값이 리턴되어 정답이 나오지 않았다.

 

 

2) 반복문

import java.io.*;

public class q2579 {
    static int[][] memory;
    static int[] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Integer N = Integer.parseInt(br.readLine());
        memory = new int[N][2];
        cost = new int[N];

        for (int i = 0; i < N; i++) {
            cost[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < N; i++) {
            for (int depth = 0; depth < 2; depth++) {
                if (i == 0 || (i == 1 && depth == 1)) {
                    memory[i][depth] = cost[i];
                } else {
                    if (depth == 1) {
                        memory[i][depth] = memory[i - 2][0] + cost[i];
                    } else if (i == 1) {
                        memory[i][depth] = memory[i - 1][1] + cost[i];
                    } else {
                        memory[i][depth] = Math.max(memory[i - 1][1], memory[i - 2][0]) + cost[i];
                    }
                }
            }
            
        }
        
        bw.write(Math.max(memory[N-1][0], memory[N-1][1]) + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

}

 

로직은 재귀문과 동일하다. 다만 buttom-up 방식에서 depth에 따른 값을 모두 저장하기 위해 이중 for문을 사용했다.

 

7. 개선점

다른 정답코드들과 비교했을 때 내가 짠 코드가 굉장히 조잡한 편이었다. 

memory[N] = Math.max(calc(N - 2), calc(N - 3) + cost[N - 1]) + cost[N];

나는은 n-1칸과 n-2칸을 밟았을 때 중의 최댓값을 구하는 것에 집중했는데, 

위의 식을 보면 (n-2칸을 밟은 경우)와 (n-3칸을 밟은경우 + n-1칸의 cost)를 비교하여 최댓값을 선택하는 방법이다.

이 방법을 사용했을 경우 depth를 사용하는 것과 중간중간의 많은 예외처리를 하지 않아도 될 것이다.

 

최종 코드

import java.io.*;

public class q2579 {
    static Integer[] memory;
    static int[] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Integer N = Integer.parseInt(br.readLine());
        memory = new Integer[N+1];
        cost = new int[N+1];

        for (int i = 1; i <= N; i++) {
            cost[i] = Integer.parseInt(br.readLine());
        }
        
        memory[0] = cost[0];
        memory[1] = cost[1];

        if (N >= 2) {
            memory[2] = cost[1] + cost[2];
        }

        bw.write(calc(N) + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int calc(int n) {
        if (memory[n] == null) {
            memory[n] = Math.max(calc(n - 2), calc(n - 3) + cost[n - 1]) + cost[n];
        }

        return memory[n];
    }

}