CosPro1급 모의고사 - Part.2 한 줄 바꾸기 - 보드게임 (C언어)

Cos Pro 1급 모의고사 - 보드게임에 대한 C언어를 이용한 저의 풀이입니다.

 

목차

• 문제 설명
• 매개변수 설명
• return 값 설명
• 예제
• 문제와 답
• ***풀이 전략***

 

문제 설명

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

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

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

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

 

매개변수 설명

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

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

 

return 값 설명

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

 

예제

grid	board_row_len	board_col_len	return
[[6,7,1,2], [3,5,3,9], [6,4,5,2], [7,3,2,6]]	4	4	38

 

문제와 답

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
 
 
int solution(int **board, int board_row_len, int board_col_len) {
    int answer = 0;
 
    int coins[4][4] = { 0, };
    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
                // Original Wrong Code
                // coins[i][j] = board[i][j] + MAX(coins[i][j], coins[i-1][j-1]);
                // Modified Code
                coins[i][j] = board[i][j] + MAX(coins[i-1][j], coins[i][j-1]);
        }
    }
 
    answer = coins[3][3];
    return answer;
}
 
 
// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다. 아래에는 잘못된 부분이 없으니 위의 코드만 수정하세요.
int main() {
    int board_row_len = 4;
    int board_col_len = 4;
    int **board = (int**)malloc(sizeof(int*) * board_row_len);
    for(int i = 0; i < board_row_len; i++)
        board[i] = (int*)malloc(sizeof(int) * board_col_len);
 
    board[0][0] = 6; board[0][1] = 7;
    board[0][2] = 1; board[0][3] = 2;
    board[1][0] = 3; board[1][1] = 5;
    board[1][2] = 3; board[1][3] = 9;
    board[2][0] = 6; board[2][1] = 4;
    board[2][2] = 5; board[2][3] = 2;
    board[3][0] = 7; board[3][1] = 3;
    board[3][2] = 2; board[3][3] = 6;
 
    int ret = solution(board, board_row_len, board_col_len);
 
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret);
}

 

풀이 전략

solution의 방법은 강화학습 기초로 나오는 동적 계획법(Dynamic Programming)과 유사한 형태로 진행한다.

점수판 board 에 대해서, 좌상단에서 우하단으로 이동할 때의 지나온 길에 대해 최대로 얻을 수 있는 코인 값을 coins에 저장한다.

배열 처리를 위한 이중 반복문

배열 형태에 대해서 점수 계산을 위한 이중 반복문 형태를 취했다.

***이동 경로에 따른 최대 코인 저장 테이블 coins***

if else는 시작점, 좌측과 상단 벽, 그리고 그 이외의 경우에 대한 처리이다.

주목할 점은 마지막의 else 이다.

지나온 경로에서 어떤 셀이 최대의 코인을 얻을 수 있으려면 최대의 코인 값을 가진 직전 지점에서 와야할 것이다.

그렇다면 탐색해야할 코인 테이블 coins에서 좌측과 윗쪽의 셀을 확인해보면 된다.

그래서 MAX(coins[i-1][j], coins[i][j-1]) 의 형태의 답이 나오게 된다.