코드업(codeup) 3703 : 사탕 줍기 1 C언어

▶문제 : 사탕 줍기 1 (codeup.kr)

사탕 줍기 1

 

▶코드 작성

#include <stdio.h>

int arr[101][101];//입력값
int memo[101][101];//최대 사탕 수

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }

    memo[1][1] = arr[1][1];//첫째줄을 채우기위해 기본값 대입
    for (int j = 2; j <= m; j++) {//첫째줄은 이전값들의 합 memo + 현재위치값 arr
        memo[1][j] = memo[1][j - 1] + arr[1][j];
    }

    int big;
    for (int i = 2; i <= n; i++) {
        memo[i][1] = memo[i - 1][1] + arr[i][1];//첫행들의 값 : 이전값들의 합 memo + 현재위치값 arr
        for (int j = 2; j <= m; j++) {
            big = memo[i][j - 1];//memo[i][j]를 기준으로 왼쪽 memo와 위쪽 memo 중 큰값을 big에 대입
            if (big < memo[i - 1][j]) big = memo[i - 1][j];
            memo[i][j] = big + arr[i][j];//big + 현재위치값 arr
        }
    }
    printf("%d", memo[n][m]);

    return 0;
}

 

▶해석

입력된 arr배열을 한 번만 거쳐서 결괏값을 구할 수 있는 방법을 생각해보았다.

그 결과 memo배열을 만들어 각 arr배열의 자리까지 도달했을 때의 최대 개수를 저장하며 n, m까지 구하는 것이다.

 

예를 들어 n=2, m=4 가 입력되고 arr배열에 입력하면 아래의 표가 나올 수 있다.

arr[1][1] = 1	arr[1][2] = 4	arr[1][3] = 2	arr[1][4] = 0
arr[2][1] = 2	arr[2][2] = 1	arr[2][3] = 3	arr[2][4] = 1

 

memo배열을 이용하여 arr배열에서 지나온 길의 최대 개수를 적어야 한다.

먼저 기준이 되기 위해 memo [1][1] = arr [1][1]을 대입하고, 오른쪽으로는 지나간 길이므로 arr배열의 값을 점차 더해준다.

arr[1][1] = 1 memo[1][1] = 1	arr[1][2] = 4 memo[1][2] = 5	arr[1][3] = 2 memo[1][3] = 7	arr[1][4] = 0 memo[1][4] = 7
arr[2][1] = 2	arr[2][2] = 1	arr[2][3] = 3	arr[2][4] = 1

 

이렇게 첫째줄이 memo배열에 입력되면 두 번째 줄부터는 더 큰 값을 비교해야 한다.

두 번째 줄의 처음 값은 비교할 값이 하나밖에 없으므로 위에 있는 memo값과 arr값을 더해준다.

arr[1][1] = 1 memo[1][1] = 1	arr[1][2] = 4 memo[1][2] = 5	arr[1][3] = 2 memo[1][3] = 7	arr[1][4] = 0 memo[1][4] = 7
arr[2][1] = 2 memo[2][1] = 3	arr[2][2] = 1	arr[2][3] = 3	arr[2][4] = 1

 

이제 memo [2][2]부터는 왼쪽에서 오는 값(memo [2][1])과 위에서 오는 값(memo [1][2])중 더 큰 값이 최대 개수이다.

큰 값을 알았으면 memo에 큰 값과 arr값을 더해준다.

arr[1][1] = 1 memo[1][1] = 1	arr[1][2] = 4 memo[1][2] = 5	arr[1][3] = 2 memo[1][3] = 7	arr[1][4] = 0 memo[1][4] = 7
arr[2][1] = 2 memo[2][1] = 3	arr[2][2] = 1 memo[2][2] = 6	arr[2][3] = 3 memo[2][3] = 10	arr[2][4] = 1 memo[2][4] = 11

최종적으로 n, m위치인 memo [2][4]가 최대 개수가 된다.