SWEA 1859 백만 장자 프로젝트

1 개요

SWEA 1859 백만 장자 프로젝트

• 뒤에서부터 최대값을 구하는 과정을 통해 해당날짜마다 그 이후로의 최대값을 기억해둔다.
• 이후로의 최대값과 같으면 차익이 없고, 최대값보다 작으면 그 차이만큼의 차익을 낼 수 있다.

SW Expert 아카데미

#	문제	풀이

2 C++

#include <iostream>
using namespace std;
int N;
int a[1000000];
int mx;
long long sum;
int main() {
	int T;
	scanf("%d", &T);
	for(int tc=1; tc<=T; tc++) {
		scanf("%d", &N);
		for (int i=0; i<N; i++) scanf("%d", &a[i]);
		sum = 0;
		mx = a[N-1];
		for(int i=N-2; i>=0; i--) {
			if( a[i] > mx) mx = a[i];
			else sum += mx - a[i];
		}
		printf("#%d %lld\n", tc, sum);
	}
}

3 Java

import java.util.Scanner;
public class Solution {
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) {
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			int N = sc.nextInt();
			int a[] = new int[N];
			for(int i=0; i<N; i++) a[i] = sc.nextInt();
			long sum = 0;
			int max = a[N-1];
			for(int i=N-2; i>=0; i--) {
				if( a[i] > max ) max = a[i];
				else sum += max - a[i];
			}
			System.out.format( "#%d %d\n", tc, sum ); 
		}
	}
}

import java.util.Scanner;
class Solution {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t=1; t<=T; t++) {
            int i, N = sc.nextInt();
            int nums[] = new int[N];
            int maxs[] = new int[N];
            for(i=0; i<N; i++) nums[i] = sc.nextInt();
            int max = 0;
            for(i=N-1; i>=0; i--) {
                if( nums[i] > max ) max = nums[i];
                maxs[i] = max;
            }
            long sum = 0;
            for(i=0; i<N; i++) sum += maxs[i] - nums[i];
            System.out.format( "#%d %d\n", t, sum ); 
        }
    }
}

4 Python

T = int(input())
for i in range(T):
    N = int(input())
    mylist = list(map(int, input().split(' ')))[::-1]  # 뒤에서부터 탐색
    answer = 0
    now_max = mylist[0]  # 현재 가장 큰 값

    for j in range(1, N):
        if now_max > mylist[j]:
            answer += now_max - mylist[j]
        else:
            now_max = mylist[j]

    print('#{} {}'.format(i+1, answer))

# https://github.com/wansang93/Algorithm