"백준 26267번: 은?행 털!자 1" 문제를 풀어봤어요!

🤔 문제 설명

프로 은행강도 시우가 은행을 털려고 한다. 시우가 달려가는 일직선 경로 위엔 $N$개의 은행이 있다. $i$번째 은행은 직선상에서 서로 다른 좌표 $X_i$에 위치하며, 시간이 정확히 $T_i$ 일 때만 문이 열려 입장할 수 있다. 또한 이 은행을 털면 $C_i$원을 얻을 수 있다.

시우는 직선 상에서 임의의 정수 좌표에서 시작해 움직인다. 움직이는 동안 좌표는 증가해야 한다 (멈춰 설 수 없음에 주의하라). 시간은 $0$으로 시작하며 좌표가 $1$만큼 증가할 때 시간도 $1$만큼 증가한다.

시우는 문이 열려 있는 은행을 마주치면 반드시 털고 가며, 매우 숙련돼있기 때문에 은행을 털어도 시간이 전혀 증가하지 않는다.

시우가 적절한 위치에서 시작했을 때, 얻을 수 있는 최대 금액을 출력하여라.

---

✅ 나의 풀이

⛰️ 실패작1

가장 비싼 금액을 기준으로 잡고 양쪽으로 계산하면 될거 같아서 해봤다.

#include <iostream>
using namespace std;

/*
백준 26267번 : 은?행 털!자 1
 */

int main() {
    int n, x;
    int maxPrice = -1;
    int sum = 0;
    int mpIndex, mpTime;
    cin >> n;

    Data *arr = new Data[n];

    for (int i = 0; i < n; i++)
    {
        cin >> x >> arr[i].t >> arr[i].c;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (maxPrice < arr[i].c)
        {
            maxPrice = arr[i].c;
            mpTime = arr[i].t;
            mpIndex = i;
        }
    }

    int t1 = mpTime;
    int t2 = mpTime;
    sum = maxPrice;
    if(mpIndex != n-1) {
        for(int i=mpIndex+1;i<n;i++) {
         if(arr[i].t > mpTime) {
            t1++;
            if(arr[i].t == t1) {
                sum += arr[i].c;
            }
         }
        }
        for(int i=mpIndex-1;i>=0;i--) {
           t2--;
            if(arr[i].t == t2) {
                sum += arr[i].c;
            }
        }

    } else {
        int t3 = mpTime;
        for(int i=mpIndex-1;i>=0;i--) {
            t3--;
            if(arr[i].t == t3) {
                sum += arr[i].c;
            }
        }
    }
}   

➡️ 실패!

⛰️ 실패작2

반복문을 돌며 모든 시간과 위치의 연속성을 찾고 일치하면 더해서 합쳐주는 방식으로 해봤다.

#include <iostream>
using namespace std;

/*
백준 26267번 : 은?행 털!자 1
 */

struct Data {
    int t;
    int c;
};

int main() {
    int n, x;
    int maxPrice = -1;
    int sum = 0;
    int mpIndex, mpTime;
    cin >> n;

    Data *arr = new Data[n];

    for (int i = 0; i < n; i++) {
        cin >> x >> arr[i].t >> arr[i].c;
    }


    for (int i = 0; i < n; i++) {
        int num = i + 1;
        sum = arr[i].c;
        for (int j = arr[i].t; j < arr[i].t + n-i; j++)
        {
            if (j == arr[num].t - 1)
            {
                sum += arr[num].c;
            }
            num++;
        }
        cout<<sum<<"\n";
        if (maxPrice < sum) maxPrice = sum;
    }

    cout << maxPrice;
}

➡️ 시간초과로 실패!

⛰️ 실패작3

🫣 열심히 삽질하다가 발견함

• 시간t에 은행의 좌표 위치에 있으려면 x-t로 은행을 털기 위해 시작해야하는 지점을 찾을 수 있다.
• 그냥 map을 쓰는거보다 unordered_map이 좋다!

• unordered_map
  • 해쉬테이블로 구현한 자료구조
  • map보다 더 빠른 탐색을 하기 위한 자료구조
  • 탐색 시간복잡도
    • unordered_map: O(1)
    • map: O(log n)
  • 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> m;
    int maxPrice = 0;

    for (int i = 0; i < n; ++i)
    {
        int x, t, c;
        cin >> x >> t >> c;
        m[t - x] += c;
        if(m[t - x] > maxPrice) maxPrice = m[t - x];
    }

    cout << maxPrice;

    return 0;
}

➡️ 실패..? 왜 안되는지 모르겟다..ㅜㅜ

😂 성공!

너무 오랜만에 c++을 사용한 나머지 int 형 변수의 범위를 까먹고 있었다. ㅋㅋ

#include <iostream>
#include <unordered_map>
using namespace std;

/*
백준 26267번 : 은?행 털!자 1
 */

int main()
{
    int n;
    cin >> n;

    unordered_map<int, long long int> m;
    long long int maxPrice = 0;

    for (int i = 0; i < n; ++i)
    {
        int x, t, c;
        cin >> x >> t >> c;
        m[x - t] += c;
        if(m[x - t] > maxPrice) maxPrice = m[x - t];
    }

    cout << maxPrice;
}

➡️ 생각을 하고 문제를 풀자ㅎㅎ