[Cos Pro 1급 java] [6차] 문제5) 코인을 많이 획득하세요

coins[i][j] = board[i][j] + Math.max(coins[i-1][j], coins[i][j-1]);

안녕하세요.

이번 포스팅은 Cos Pro 1급 java 6차 기출 문제 중 5번 문제인 코인을 많이 획득하세요를 풀어보겠습니다.

 

처음에 BFS를 이용해서 풀어야 하나 싶었는데

굳이 그렇게 안해도 풀리는 것 같더라구요..

 

□ 문제설명

A 게임은 4x4 격자 모양의 보드의 가장 왼쪽 위에서 가장 오른쪽 아래로 말을 이동시키면서 각 구역에 있는 코인을 획득하는 게임입니다. 이때, 말은 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.

예를 들어, 보드가 아래와 같다면

아래의 경우가 코인을 최대로 획득할 수 있는 경우이고 이때 획득하는 코인은 38입니다.

각 구역에서 획득할 수 있는 코인 양을 담은 2차원 배열 board, board의 길이 board_len이 매개변수로 주어질 때, 최대로 획득할 수 있는 코인의 양을 return 하도록 solution 함수를 작성했습니다. 그러나, 코드 일부분이 잘못되어있기 때문에, 몇몇 입력에 대해서는 올바르게 동작하지 않습니다. 주어진 코드에서 한 줄만 변경해서 모든 입력에 대해 올바르게 동작하도록 수정하세요.

---

□ 매개변수 설명

각 구역에서 획득할 수 있는 코인 양을 담은 2차원 배열 board, board의 길이 board_len이 solution 함수의 매개변수로 주어집니다.

• board는 4x4 크기인 2차원 배열입니다.
• board_len은 항상 4 입니다.
• 각 구역에서 획득할 수 있는 코인의 양은 1 이상 9 이하인 자연수입니다.

---

□ return 값 설명

최대로 획득할 수 있는 코인의 양을 return 합니다.

---

□ 예시

board	board_len	return
[[6, 7, 1, 2], [3, 5, 3, 9], [6, 4, 5, 2], [7, 3, 2, 6]]	4	38

---

□ 예시설명

문제에 나온 예와 같습니다.

 

※ 초기 소스코드

class Main {
    public int solution(int[][] board) {
        int answer = 0;

        int[][] coins = new int[4][4];
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                if(i == 0 && j == 0)
                    coins[i][j] = board[i][j];
                else if(i == 0 && j != 0)
                    coins[i][j] = board[i][j] + coins[i][j-1];
                else if(i != 0 && j == 0)
                    coins[i][j] = board[i][j] + coins[i-1][j];
                else
                    coins[i][j] = board[i][j] + Math.max(coins[i][j], coins[i-1][j-1]);
            }
        }

        answer = coins[3][3];
        return answer;
    }

	// 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다. 아래에는 잘못된 부분이 없으니 위의 코드만 수정하세요.
    public static void main(String[] args) {
        Main sol = new Main();
        int[][] board = {{6, 7, 1, 2}, {3, 5, 3, 9}, {6, 4, 5, 2}, {7, 3, 2, 6}};
        int ret = sol.solution(board);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret + " 입니다.");
    }
}

 

※ 틀린 소스코드

coins[i][j] = board[i][j] + Math.max(coins[i][j], coins[i-1][j-1]);

여기서 보면 이동 방식은 대각선으로 갈 수 없습니다.

이동 방식은 i+1이거나 j+1이어야 합니다.

 

※ 고친 소스코드

coins[i][j] = board[i][j] + Math.max(coins[i-1][j], coins[i][j-1]);