[2851번] 슈퍼 마리오 (Dynamic Programming)

문제 출처 : 

https://www.acmicpc.net/problem/2851

알고리즘 분석 :

이 문제는, Dynamic Programming을 기반으로 풀어도 되고, 다르게 풀어도 된다.

만약 10 20 30 40 50 60 70 80 90 100이 있었다면

이 문제의 조건 대로 한다면, 

10 30 60 100 100 100 100 100 100 100일 것이다.

따라서 이때는 출력이 100이 나올 것이다.

만약 다른 예로 1 10 2 30 3 5 9 39 2 60라면

1 11 13 43 46 51 60 99 101 101일 것이다.

따라서 이때는 출력이 99가 아닌 101이 나올 것이다.

자세한 알고리즘은 소스 코드 주석으로 달아 놓았다. 

소스 코드 : 

#include <stdio.h>
//#include <time.h>
 
int main()
{
    int i, j, distance = 0, final = 0;
    int arr[11] = { 0, }; // 배열 받는 곳
    int ans[11] = { 0, }; // DP에 이용
    int tmp[11] = { 0, }; // 100과의 거리를 나타내기 위해 이용
 
    //임의의 값을 자동으로 넣어 테스트 할 수 있는 코드
    //srand((unsigned int)time(NULL));
 
 
    //for (i = 1; i <= 10; i++)
    //{
    //    arr[i] = rand() % 99;
    //    printf("%d\n", arr[i]);
    //}
 
    for (i = 1; i <= 10; i++)
        scanf("%d", &arr[i]);
 
    for (i = 1; i <= 10; i++)
    {
        for (j = 1; j <= i; j++)
        {
            // 100의 합이 나오면 그냥 출력 후 종료
            if (ans[i] == 100)
            {
                printf("100");
                return 0;
            }
 
            // 100보다 작으면 계속 더해간다.
            if (ans[i] < 100)
                ans[i] = ans[i] + arr[j];
 
            // 100보다 클 때, 100보다 커지기 전의 값과 100보다 커진 값 이 두 값의
                  // 100과의 거리를 비교하여 저장한다.
            else if (ans[i] > 100)
            {
                if (ans[i] - 100 > 100 - (ans[i] - arr[j - 1]))
                    ans[i] = ans[i] - arr[j - 1];
 
                break;
            }
        }
    }
 
    // 100과의 거리를 저장하는 배열 tmp[]
    for (i = 1; i <= 10; i++)
    {
        //    printf("ans :: %d\n", ans[i]);
        if (ans[i] > 100)
            tmp[i] = ans[i] - 100;
 
        else
            tmp[i] = 100 - ans[i];
    }
 
    // 가장 가까운 거리를 가진 배열 값을 찾는다.
    distance = tmp[1];
 
    for (i = 2; i <= 10; i++)
    {
        if (tmp[i] < distance)
            distance = tmp[i];
    }
 
 
    // ex) 99과 101이 있었다면 99는 100과 거리가 1이니 1 + 100 == 101 
     //(존재하므로 101을 출력하도록)
    for (i = 1; i <= 10; i++)
    {
        if (distance + 100 == ans[i])
        {
            final = ans[i];
            break;
        }
        else
            final = 100 - distance;
 
    }
 
    printf("%d", final);
 
    return 0;
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>