백만장자 프로젝트 C++(SW Expert Academy)

난이도 : D2

문제번호 : 1859

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

불러오는 중입니다...

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

4. 결과

 

---

1. 문제 설명

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다. 다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다. 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.     1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.     2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.     3. 판매는 얼마든지 할 수 있다. 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 각 날의 매매가는 10,000이하이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

예시

입력	출력
3 3 10 7 6 3 3 5 9 5 1 1 3 1 2	#1 0 #2 10 #3 5

 

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다. 2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

 

---

2. 문제풀이

처음에는 단순하게 뒤에거보다 쌀때만 앞의 주식을 구매했습니다.(즉 앞에서부터 계산) 그렇지만 계속 틀렸고 팔수있는 최대가격일때 팔면 처리되지 않을까 라는 생각에 문제를 풀어봤습니다. 뒤에서부터 계산을 시작했고 제일 뒤에값을 기준으로 점차 앞으로 나갔습니다. 만약 현재값보다 커지는 값이 나온다면 최대 판매가를 수정하고 이보다 적은것은 이익으로 추가했습니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int length, m_length, t, count = 1;
    cin >> length;
    while (length--) {
        cin >> m_length;
        vector<int> list;
        long long answer = 0;
        while (m_length--) {
            cin >> t;
            list.push_back(t);
        }
        int max = *--list.end();
        for (int i = list.size() -2 ; i >= 0  ; i--) {
            if(list[i] <= max)          answer += max - list[i];
            else      max = list[i];
        }
        cout << "#" << count++ << " " << answer << endl;
    }
    return 0;
}

3.2 주석있는 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int length, m_length, t, count = 1;
    //총 반복할 횟수
    cin >> length;
    while (length--) {
        //내부 입력받는 횟수
        cin >> m_length;
        //벡터에 리스트를 저장
        vector<int> list;
        //
        long long answer = 0;
        //모든 입력을 vector에 추가
        while (m_length--) {
            cin >> t;
            list.push_back(t);
        }
        //기준이 될값을 저장(벡터의 제일 마지막부분)
        int max = *--list.end();
        //벡터의 마지막 전부터 처음까지 반복한다.
        for (int i = list.size() -2 ; i >= 0  ; i--) {
            //기준값보다 적을경우 이득추가
            if(list[i] <= max)          answer += max - list[i];
            //아니라면 기준값 변경
            else      max = list[i];
        }
        cout << "#" << count++ << " " << answer << endl;
    }
    return 0;
}

 

4. 결과