CosPro1급 모의고사 - Part.2 한 줄 바꾸기 - 종이접기 (C언어)

Cos Pro 1급 모의고사 - 종이접기에 대한 C언어를 이용한 저의 풀이입니다.

 

목차

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

 

문제 설명

4 x 4 크기인 정사각형 종이가 1 x 1 크기인 격자 칸으로 나누어져 있습니다. 이 종이를 가로축 혹은 세로축에 평행한 격자 선을 따라 한 번 접었을 때, 만나는 격자 칸에 적힌 숫자의 합이 최대가 되도록 하려 합니다. 종이를 접을 때는 만나는 격자 칸이 정확히 일치하도록 해야 합니다.

예를 들어 다음과 같이 4 x 4 크기인 종이가 있을 때,

종이는 점선 중 하나를 따라서 접을 수 있습니다. 이때, 붉은색 점선을 따라 종이를 접으면 36과 19가 적힌 칸이 정확히 만납니다. 두 숫자의 합은 55이며, 이때가 최댓값입니다.

4 x 4 크기인 정사각형 종이의 각 격자 칸에 적힌 숫자가 담긴 배열 grid, grid의 행 길이 grid_row_len, grid의 열 길이 grid_col_len이 매개변수로 주어질 때, 종이를 접었을 때 만나게 되는 격자 칸에 적힌 숫자의 합 중 최댓값을 return 하도록 solution 함수를 작성했습니다. 그러나, 코드 일부분이 잘못되어있기 때문에, 몇몇 입력에 대해서는 올바르게 동작하지 않습니다. 주어진 코드에서 한 줄만 변경해서 모든 입력에 대해 올바르게 동작하도록 수정하세요.

 

매개변수 설명

4 x 4 크기인 정사각형 종이의 각 격자 칸에 적힌 숫자가 담긴 배열 grid, grid의 행 길이 grid_row_len, grid의 열 길이 grid_col_len이 매개변수로 주어집니다.

• 각 격자칸에 적힌 수는 1 이상 100 이하인 자연수입니다.
• grid_row_len, grid_col_len은 항상 4입니다.

 

return 값 설명

격자 선을 따라 종이를 한 번 접었을 때 만나는 격자 칸에 적힌 숫자의 합 중 최댓값을 return 해주세요.

• 격자 선은 문제의 예제와같이 가로, 혹은 세로 방향으로 평행한 점선을 말합니다.

 

예제

grid	grid_row_len	grid_col_len	return
[[1,4,16,1] [20,5,15,8] [6,13,36,14] [20,7,19,15]]	4	4	55

 

문제와 답

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
 
int max(int a, int b){
    return a < b ? b : a;
}
 
int solution(int **grid, int grid_row_len, int grid_col_len) {
    int answer = 0;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            for(int k = j + 1; k < 4; k += 2)
                // answer = max(answer, max(grid[i][j] + grid[j][k], grid[j][k] + grid[k][i])); // Original wrong code
                answer = max(answer, max(grid[i][j] + grid[i][k], grid[j][i] + grid[k][i])); // Modified code
    return answer;
}
 
// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다. 아래에는 잘못된 부분이 없으니 위의 코드만 수정하세요.
int main() {
    int grid_row_len = 4;
    int grid_col_len = 4;
    int **grid = (int**)malloc(sizeof(int*) * grid_row_len);
    for(int i = 0; i < grid_row_len; i++) {
        grid[i] = (int*)malloc(sizeof(int) * grid_col_len);
    }
 
    grid[0][0] = 1; grid[0][1] = 4;
    grid[0][2] = 16; grid[0][3] = 1;
    grid[1][0] = 20; grid[1][1] = 5;
    grid[1][2] = 15; grid[1][3] = 8;
    grid[2][0] = 6; grid[2][1] = 13;
    grid[2][2] = 36; grid[2][3] = 14;
    grid[3][0] = 20; grid[3][1] = 7;
    grid[3][2] = 19; grid[3][3] = 15;
 
    int ret = solution(grid, grid_row_len, grid_col_len);
 
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret);
}

 

풀이 전략

격자 탐색을 위한 이중 반복문

solution 함수를 보면 모든 격자를 탐색하도록 인자 i, j를 이용한 이중 반복문으로 구성되어있다.

종이접기 규칙을 검사하는 반복문

그 최하단에 어떤 for 반복문이 있는데 이게 종이접기의 규칙에 맞추어서 검사하는 반복문이다.

어떤 셀의 아래로 접었을 때, 바로 아랫칸(+1)과 만나거나 다음 4번째 칸(+3)에 만나는 경우가 있다.

이를 위해서 for 반복문의 증감식 k+=2 의 의미가 접는 위치에 따라서 만나는 칸은 2를 더한 만큼이라는 것이다.

최대 비교 - 풀이 초점

문제에는 배열의 인덱스가 아무렇게나 넣어져있다.

굳이 접은 줄들의 칸을 가지고 비교할 필요가 없다.

왜냐하면 접었을 때 "최댓값만" 찾으면 되기 때문이다.

아랫방향이던 오른쪽 방향이던 비교만 하면 된다.

그러면 (1,1)을 예로 하면 max 함수 내부에는 서로 만나는

아래로 한칸, 우측으로 한칸 비교,

아래로 세칸, 우측으로 세칸 비교

를 하면 된다.