[SWEA/C++] 1859 백만 장자 프로젝트

SWEA 1859번 백만 장자 프로젝트 문제 

 

SWEA 1859 백만 장자 프로젝트 입/ 출력 및 예제 풀이 

 

백만 장자 프로젝트를 보면 결국에는 입력된 모든 수를 알고 그 수의 max 값을 안 다음에 그 max값에 그 앞의 수들을 뺀 값을 result에 더 해주면 된다.

 

만약 max 값이 5이고, 그 앞의 값들이 3, 4 라면

result + = 5 - 3;

result += 5 - 4;

이런 식으로 값을 추가해줘서 총 최대 이득을 뽑으면 된다.

 

하지만, 1 1 4 1 3 처럼 중간에 큰 max 값이 나오고, 마지막에 3 같은 다음 max 값이 나온다면 4의 max 값 뒤로 다시 max 값을 지정해줘야 한다. 

 

while (point < size) {

		for (int i = point; i < size; i++) {
			if (list[num][i] > max) {
				max = list[num][i];
				max_num = i;	
			}
		}
		if (point == max_num) point++;
		else if (point < max_num) {
			for (int i = point; i < max_num; i++) {
				result += max - list[num][point];

				//cout << "list : " << list[num][point] << '\n';
				point++;
			}
		}
		//point++;

	}

 

그래서, 이렇게 loop를 돌면서 주어진 수의 max 값을 찾고 그 max 값까지 값들을 계산해서 result에 추가해준 다음 또 max값을 찾는 loop를 만들어줬다. 

 

또한, max 값이 맨 처음 나오고 뒤에 수들이 작을 경우에는 어떻게 하는게 나을까?

예를 들어, 5 1 1 1 3 이렇게 나왔다면, 5가 max 지만 그 앞의 값들이 없기 때문에 의미가 없다. 

따라서, 나는 현재 위치를 point 값을 줘서 찍어줬고, 만약 point 값과 max_num (max의 위치) 값이 같으면 point를 ++ 해주고 다시 loop를 처음부터 돌게 만들었다. 

 

		if (point == max_num) point++;
		else if (point < max_num) {
			for (int i = point; i < max_num; i++) {
				result += max - list[num][point];

				//cout << "list : " << list[num][point] << '\n';
				point++;
			}
		}

요렇게 해주고, 같지 않으면 result 계산 식으로 넘어가게 만들어서 백만 장자 프로젝트 코드의 구성을 해줬다.

 

 

---

1859 백만 장자 프로젝트 전체 코드 

#include<iostream>
#include<vector>
#include<stdio.h>

using namespace std;

int list[10][1000002];


void cacl(int num, int size) {
	int max = 0;
	int max_num = 0;
	int point = 0;
    long result = 0;


	while (point < size) {

		for (int i = point; i < size; i++) {
			if (list[num][i] > max) {
				max = list[num][i];
				max_num = i;	
			}
		}
		if (point == max_num) point++;
		else if (point < max_num) {
			for (int i = point; i < max_num; i++) {
				result += max - list[num][point];

				point++;
			}
		}

	}

	cout << result << '\n';

}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin>>T;
    int num = 0;

	for(test_case = 0; test_case < T; ++test_case)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> list[num][i];
		}

		cout << "#" << num+1 << " ";
		cacl(num, n);
		num++;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}