[ SWEA 7812 ] 옥히의 OK! 부동산 (C++)

SWExpertAcademy의 옥히의 OK!부동산(7812 / D5) 문제이다.

[ 문제풀이 ]

주어진 1 x N 크기의 땅에서, M원으로 연속으로 이어진 땅을 투자할 수 있는 방법을 구해야 하는 문제이다.

그럼 주어진 테스트케이스 중, 2번 케이스를 통해서 한번 알아보자.

[ 1 3 2 5 4 6 2 1 3 2 ] , M = 6 인 경우이다.

아직, 투자를 하나도 하지 않은 상태이므로 초기에 사용한 자금은 0원이 된다.

그리고 땅을 순차적으로 탐색하면서 투자했을 때, 소모되는 자금을 적어보면..

첫 번째 땅[1] = 1원

두 번째 땅[3] = 4원 (첫 번째 땅에서 1원을 소모 , 두 번쨰 땅에서 3원을 소모 = 4원 소모)

세 번째 땅[2] = 6원 (1 + 3 + 2)

지금보면, 1번땅 ~ 3번땅 까지 연속적으로 이어진 땅에 투자를 했더니, 6원이 딱 맞춰졌다.

즉 ! 6원을 모두 사용해서 투자할 수 있는 경우이다.

이어서 계속해보자.

네 번째 땅[5] = 11원(1 + 3 + 2)

이 경우에는, 우리에게 주어진 M원을 초과하는 상황이 발생한다. 즉 ! 이 경우에는 그 이후에 나오는 땅들을 연속적으로 탐색을 할 수가 없다. 왜냐하면 이미 M원을 초과해 버렸기 때문에 저 탐색해봤자, 절대로 M원으로 투자할 수 있는 방법이 존재하지 않기 때문이다.

따라서, 이 경우에는 기존에 선택했던 땅들 중에서 일부를 포기해주어야 한다.

그럼 어떤 일부를 포기해야할까 ?? 바로 "포기함으로써, 6원 이하가 될 때까지" 포기를 해 주어야 한다.

가장 처음에 선택했던 첫 번째 땅을 포기해보자.

그럼, 현재 11원에서 1원만큼을 돌려받는 상황이니, 10원이 된다. 하지만, 그럼에도 6원을 넘어버렸기 때문에, 그 다음 땅을 포기해보자. 그럼, 10원에서 3원만큼을 돌려받는 상황이니, 7원이 된다. 하지만 여전히 6원을 넘어버렸다.

세 번째 땅도 포기를 하면, 7원에서 2원을 빼니 5원이 된다. 즉 ! 네 번쨰 땅에 투자를 하기 위해서는, 기존에 투자를 했던, 1번, 2번, 3번 땅들을 포기해야 한다. 그럼 현재까지 투자한 금액은 5원이 된다.

다섯 번째 땅[4] = 9원(기존의 투자한 금액 5원 + 4원)

이 경우에도 또 넘어버리게 된다. 마찬가지로 이전에 투자했던 땅들을 포기해보자. 그럼 네번째 땅을 포기해버리면, 4원이 된다.

이런식으로, 투자를 진행해 나가면 된다.

정리를 해보면...

1. 1번 땅부터 N번 땅 까지 순차적으로 투자를 해 볼 것이다.

2. 그런데, "현재 땅에 투자를 함으로써 소비되는 금액이 M원보다 더 클 경우" 기존에 투자를 했었던 땅들 중 일부를

   순차적으로 포기를 해주어야 한다.

3. 만약, 투자를 하는 도중 "투자한 금액 = M원" 인 경우가 발생하면, 투자할 수 있는 방법의 수++

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N, M, Answer;
int Arr[MAX];
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    int First_land = 1;
    int Cost = 0;
    for (int i = 1; i <= N; i++)
    {
        Cost = Cost + Arr[i];
        while (Cost > M) Cost = Cost - Arr[First_land++];
        if (Cost == M)    Answer++;
        
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}