[SWEA] 1859번 백만 장자 프로젝트

1859 백만 장자 프로젝트

문제는 불법 복사가 금지되어있어서 풀이만 쓰겠다.

풀이)

일단, N일동안의 매매가를 배열에 저장해 둔다. 

그리고 

1. 처음 인덱스부터 마지막인덱스( 0 ~ n - 1 ) 값 중 가장 큰 값의 마지막 인덱스(i)를 찾는다.

2. (0번째 인덱스 ~ i - 1)까지 이득을 구한다.

    이득은 array[i] - 각 인덱스의 값 들의 합.

3. i + 1 부터 마지막 인덱스 n - 1까지 중 가장 큰 값의 마지막 인덱스(j)를 찾는다.

4. (i+1 인덱스 ~ j)까지 이득을 구한다.

3, 4번을 현재 인덱스가 n - 1까지 계속 반복하면 된다.

예를 들어)

 N=6, 매매가 1,1,3,1,1,2일 때 계산 과정을 본다면

주의

매매가의 최고값이 10,000이고, N은 1,000,000개까지 있을 수 있으니깐

이득 변수의 자료형을 int가 아닌 long long 으로 두어야한다.

코드)

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1000001];
int n;
 
int findMax(int idx) {
    int tmp = 0;
    int tmpx = 0;
    for (int i = idx; i < n; i++) {
        if (tmp < arr[i]) {
            tmp = arr[i];
            tmpx = i;
        }
        else if (tmp == arr[i]) {
            tmpx = i;
        }
    }
    return tmpx;//최고값의 마지막 인덱스 return
}
 
int main(int argc, char** argv)
{
    int test_case = 0;
    int T = 0;
 
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    for (test_case = 1; test_case <= T; ++test_case)
    {
 
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        long long profit = 0;
        
        for (int i = 0; i < n;) {
            int goal = findMax(i);
            while (i != goal)
            {
                profit += arr[goal] - arr[i];
                i++;
            }
            i++;
        }
        printf("#%d %lld\n", test_case, profit);
        fill(arr, arr + n, 0);
    }
    return 0;
}