백준 17521번 문제 ( Byte Coin )

문제 출처 : https://www.acmicpc.net/problem/17521

17521번: Byte Coin

이 문제는 예전 ICPC 출전하였을때 다른 팀원이 풀고 내가 풀어보지 못한 문제였다.

그래프에서 모든 값을 알 수 있으니 높낮이의 아래와 위를 찾아서 계산을 해주면 되는 문제이다.

계산을 하면 할수록 값이 커져서 int 값을 초과할 수 있으니 long long int를 써야하는 문제이기도 하다. 

아래는 해당 문제를 해결한 소스이다. 

#include<stdio.h>
#pragma warning(disable:4996)
int arr[16];
int main()
{
    int n;
    int w;
    int j;
    int temp=0;
    int save_min = 0;
    int save_max = 0;
    scanf("%d %d", &n, &w);
    long long int value = 0;
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    value = value + w;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > arr[save_min])
        {
            save_max = i;
            for (j = i; j < n; j++)
            {
                if (arr[j] < arr[save_max])
                {
                    temp = j;
                    break;
                }
                else
                    save_max = j;
            }
            value = (value / arr[save_min]) * arr[save_max] + value % arr[save_min];
            save_min = temp;
            i = j;
        }
        else
            save_min = i;
    }
    printf("%lld", value);
}