어느 게임 개발자의 기록

1 - 3 - 10 - 5 - 2 - 3 이렇게 6일의 주식이 주어졌다고 가정해보자.

각 일자를 기준으로, 주식을 구매했다면 뒤의 날중 가장 비싼 날에 판매하는 것이 가장 이익이 극대화 될 것이다.

맨 첫날의 주식의 경우, 1원이기 때문에 뒤의 날중 가장 비싸게 팔 수 있는 3번째날에 판매하는 것이 이익이 최대일 것이다.

반면, 4번째 날의 경우, 뒤의 날중 5원 이상으로 팔 수 있는 날이 없다.

그러므로 4번째 날의 주식은 구매하지 않는 것이 가장 좋다.

정리해보자면 뒤의 날중 최대 주식 가격이 구매 가격보다 비싸다면 그 날 판매해야하고,

구매 가격보다 저렴하다면 주식을 구매하지 말아야 한다.

이를 위해, 배열의 원소마다 뒤쪽의 값을 모두 검사해서 최대값을 구해서 확인할 수도 있겠지만, N의 최대가 1,000,000이기 때문에, 시간초과가 발생할 수 밖에 없다.

본인은 이런 방식을 사용하였다.

먼저, MaxStock이라는 변수를 하나 선언하였다.

1 - 3 - 10 - 5 - 2 - 3 의 배열이 주어졌다면, 뒤에서 부터 역으로 검사하며 MaxStock을 계속 갱신하며 이익을 더해주었다.

MaxStock = 0;

Profit = 0;

6일차 - 3원 ( MaxStock < 3) -> MaxStock = 3;

6일차에선, MaxStock보다 주식의 가격이 높기 때문에 3원으로 갱신해주었다.

5일차 - 2원 (MaxStock> 2) -> 갱신 X

Profit += MaxStock - (2원); 

5일차에선 MaxStock이 주식 가격보다 높기 때문에, 값을 갱신하지 않았다.

이 때, 5일차의 주식은 뒤의 날중 가장 비싼 주식의 가격인 MaxStock의 값에 주식을 판매하는 것이 가장 효율적이기 때문에, 주식을 MaxStock 가격에 판매하였다.

4일차 - 5원 (MaxStock < 5) -> MaxStock = 5;

3일차 - 10원 (MaxStock < 10) -> MaxStock = 10;

2일차 - 3원 (MaxStock > 3) -> 갱신X , Profit += MaxStock - (3원); 

1일차 - 1원 (MaxStock > 1) -> 갱신X , Profit += MaxStock - (1원); 

이처럼, 뒤에서부터 MaxStock을 최대값으로 갱신하며 앞으로 탐색하게 되면 주식은 반드시 MaxStock에 판매하는 것이 이득일 수 밖에 없다. (MaxStock은 뒤의 날중 최대 가격이기 때문에)

또한, 뒤의 날중 최대 가격인 MaxStock이 현재 가격보다 저렴하다면, 주식을 판매하지 않고 최대 주식 가격을 갱신하기 때문에 더 저렴한 가격에 주식을 팔아 손해보는 일도 발생하지 않는다.

이렇게 로직을 짜면, 1번의 반복문만 돌면 되기 때문에 O(n)의 시간복잡도를 가지게 된다.

풀이 코드

먼저 입력이다. TestCase의 수를 입력받고, TestCase의 수 만큼 출력해야하는 답이 존재하기 때문에 답을 보관할 vector를 선언하였다.

int NumOfTestCase = 0;
std::cin >> NumOfTestCase;

std::vector<long long> Answers;
Answers.reserve(NumOfTestCase);

다음은, 총 며칠이 주어지는 지와 주식 가격에 대한 정보를 입력받았다.

그 이후, 위에서 설명한 것과 같이 맨 뒤에서부터 앞으로 탐색하며 MaxStock의 가격을 갱신하였고,

현재 주식 가격보다 MaxStock이 더 비싸다면 주식을 판매하여 이익을 증가시켰다.

for (int i = 0; i < NumOfTestCase; i++)
{
    int Days = 0;
    std::cin >> Days;

    std::vector<int> Stocks(Days);
    for (int i = 0; i < Days; i++)
    {
        std::cin >> Stocks[i];
    }

    long long MaxStock = 0;
    long long Profit = 0;

    for (int i = Days - 1; i >= 0; i--)
    {
        if (MaxStock < Stocks[i])
        {
            MaxStock = Stocks[i];
        }
        else
        {
            Profit += MaxStock - Stocks[i];
        }
    }

    Answers.push_back(Profit);
}

마지막으로 출력해주면 된다.

for (int i = 0; i < NumOfTestCase; i++)
{
    std::cout << Answers[i] << "\n";
}

여기서 주의해야 할 점은 답을 int형이 아닌 long long 형으로 저장해야 한다는 것이다.

int형으로 저장하고 출력하게 되면, 오답처리가 된다. 

전형적인 플로이드 워셜 알고리즘 문제이다.

n개의 도시중 두 도시를 지나는 버스들이 있고, 버스마다 비용이 다른 상황에서

도시와 도시를 지나는 최단 비용을 구하는 문제이다.

이런 최단 비용을 탐색하는 알고리즘은 대표적으로 플로이드 워셜, 다익스트라가 있다. 플로이드 워셜은 모든 지점에서 모든 지점으로의 최소 비용을 모두 구할 수 있지만, 다익스트라는 하나의 시작 지점에서 부터 모든 지점으로의 최소 비용을 계산할 수 있다.

다만, 플로이드 워셜은 O(n^3)이라는 무지막지한 시간복잡도를 보유하고 있기 때문에 노드의 수가 약 400개 이하일 때만 사용할 수 있다고 생각하면 된다.

먼저 입력과 초기화에 대한 코드이다.

int NumOfCity = 0;
int NumOfBus = 0;

std::cin >> NumOfCity >> NumOfBus;

std::vector<std::vector<int>> Cost(NumOfCity, std::vector<int>(NumOfCity, 50000000));

for (int i = 0; i < NumOfBus; i++)
{
	int Start = 0;
	int End = 0;
	int BusCost = 0;

	std::cin >> Start >> End >> BusCost;

	Cost[Start - 1][End - 1] = std::min(Cost[Start - 1][End - 1], BusCost);
}

for (int i = 0; i < NumOfCity; i++)
{
	Cost[i][i] = 0;
}

도시의 수와 버스의 수를 먼저 입력받은 뒤, 도시의 수를 높이, 너비로 가진 이차원 벡터를 구성해주었다.

연결되지 않은 도시를 표현하기 위해 50000000이라는 큰 숫자로 먼저 벡터의 원소들을 초기화 하였다.

이후, 버스의 정보를 입력받았다.

어디서 시작되어 어디까지 가는지, 비용은 얼마인지 3가지 정보가 입력된다.

동일한 구간이 다른 비용으로 여러 번 입력될 수도 있기 때문에, Cost[Start - 1][End - 1] 은 기존의 값과 새로 입력되는 값중 최소값으로 설정해주었다.

입력을 모두 받은 이후, i와 j가 같은 지점의 Cost는 모두 0으로 설정해주었다.

(시작지점과 도착지점이 같다면, 비용이 들지 않기 때문이다.)

for (int i = 0; i < NumOfCity; i++)
{
    for (int j = 0; j < NumOfCity; j++)
    {
        for (int k = 0; k < NumOfCity; k++)
        {
            Cost[j][k] = std::min(Cost[j][k], Cost[j][i] + Cost[i][k]);
        }
    }
}

이후, 무식하게 3중 반복문을 돌리면 이게 플로이드 워셜 알고리즘 끝이다.

j -> k로 가는 비용과 j -> i -> k 처럼 i를 거쳐가는 비용중 더 저렴한 값으로 Cost를 갱신하는 과정을

모든 지점에 대해서 반복하면 된다.

반복문이 모두 끝나고 나면, 배열의 모든 값은 최소값으로 갱신되어 있을 것이며, 이동할 수 없는 지점의 값은 최초에 초기값으로 설정해둔 50000000이 들어있을 것이다.

for (int i = 0; i < NumOfCity; i++)
{
    for (int j = 0; j < NumOfCity; j++)
    {
        if (Cost[i][j] == 50000000)
        {
            Cost[i][j] = 0;
        }

        std::cout << Cost[i][j] << " ";
    }

    std::cout << "\n";
}

이후 출력하면 된다. 다만, 문제의 경우엔 도착할 수 없는 지점은 0으로 표기하라고 되어있기 때문에

값이 50000000인 지점은 모두 0으로 변경해준 뒤에 출력해야 한다.

알고리즘이 명확한 문제인 만큼, 대부분 속력과 메모리 사용량이 고만고만 하게 나온다.

플로이드 워셜이라는 알고리즘을 알고 있다면 상당히 간단하게 풀리는 문제이다.

그렇기 때문에 간단한 문제에서 헤메지 않으려면 알고리즘에 대한 지식은 꾸준히 늘리는 것이 좋을 것 같다.

1~N 명이 앉아있고, 1부터 시작해서 K번째에 있는 사람을 제거하는 문제이다.

예를 들어, N이 10이고 K가 3이라고 가정하자.

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 1

이런 식으로 순서대로 10명이 앉아있으며, 원형이기 때문에 마지막 10번 사람의 옆엔 1번이 위치하게 된다.

K가 3이라면, 맨 처음 3번째에 존재하는 3이 제거된다.

1 - 2 - 공석 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 1

3이 제거되었고, 기존 3의 자리는 공석이 되었으므로 사람들의 위치관계를 정리하면 위와 같이 된다.

3의 기존 자리를 기준으로 다시 K번만큼 수를 세고 나면, 6번이 선택되므로 다음은 6번이 제거된다.

1 - 2 - 공석 - 4 - 5 - 공석 - 7 - 8 - 9 - 10 - 1

동일하게, 반복하면 다음은 9번이 제거되며, 그 다음은 2번이 제거된다. 계속 반복하여 모두 제거될 때 까지 진행하면 된다.

문제를 푸는 방법은 여러가지가 있겠지만, 본인은 std::list를 활용하여 해결하였다.

처음엔 std::vector를 이용하여 공석을 모두 고려하여 해결하였지만, 매 탐색마다 공석의 위치를 고려하는 것 때문에 제출 후 시간이 830ms 정도가 나왔다.

이후, list를 이용하여 공석을 모두 제거하고 남아있는 사람만을 기준으로 탐색을 하게 되니, 100ms까지 줄어들었다.

문제 해결

먼저 입력과 초기화에 관한 코드이다.

int N = 0;
int K = 0;

std::cin >> N >> K;

std::list<int> Person(N);
std::list<int>::iterator Iter = Person.begin();

int PersonIndex = 1;
while (Iter != Person.end())
{
    *Iter = PersonIndex;

    Iter++;
    PersonIndex++;
}

N과 K를 입력받았고, N의 크기만큼 list를 resize하였다.

이후, List를 순회하며 값을 1~N까지 순서대로 입력해주었다.

std::queue<int> Delete;

int Count = 1;
Iter = Person.begin();

while (Delete.size() < N)
{
    if (Iter == Person.end())
    {
        Iter = Person.begin();
    }

    if (Count == K)
    {
        Count = 0;
        Delete.push(*Iter);
        Iter = Person.erase(Iter);
        Count++;

        continue;
    }

    Iter++;
    Count++;
}

문제 해결 코드이다.

먼저, 제거된 사람들을 순서대로 출력하는 것이 문제의 목표이기 때문에,

제거되는 사람들을 순서대로 queue에 집어넣고 추후 pop하여 순서대로 출력하기 위해 queue를 하나 선언하였다.

이후, Iterator를 돌며 순회하였다. 순회하면서 Count 를 1씩 증가시키며 몇 번을 건너뛰었는지 계산한 뒤, 이 값이 k와 같다면 해당 사람을 제거하였다.

맨 끝 지점의 사람의 옆엔 첫번째 사람이 앉아있는 원탁구조이기 때문에, 이터레이터가 end를 가리킬 때엔 값을 begin으로 변경해주었다.

이후, 모두 제거되었을 때 반복문이 종료된다.

모두 제거되는 조건을 list의 size() 가 0일 때로 계산할 수도 있지만, 본인은 queue의 size (제거된 사람의 수)가 전체 인원 수와 동일해질 때 반복문을 종료하였다.

std::cout << "<";
while (Delete.size() > 0)
{
    int CurIndex = Delete.front();
    Delete.pop();

    std::cout << CurIndex;

    if (Delete.size() > 0)
    {
        std::cout << ", ";
    }
}

std::cout << ">";

다음은 출력이다.

출력을 <1, 2, 3, 4, 5 > 이런 식으로 출력해야 하기 때문에

처음엔 <를 출력하고 끝엔 >를 출력하였다.

이후 원소를 하나씩 출력하였고, 마지막 원소를 제외하고는 모두 원소를 출력한 뒤에 ", "를 추가로 출력해주었다.

아래는 전체 코드이다.

int main()
{
	int N = 0;
	int K = 0;

	std::cin >> N >> K;

	std::list<int> Person(N);
	std::list<int>::iterator Iter = Person.begin();
	
	int PersonIndex = 1;
	while (Iter != Person.end())
	{
		*Iter = PersonIndex;
		
		Iter++;
		PersonIndex++;
	}

	std::queue<int> Delete;
	
	int Count = 1;
	Iter = Person.begin();

	while (Delete.size() < N)
	{
		if (Iter == Person.end())
		{
			Iter = Person.begin();
		}

		if (Count == K)
		{
			Count = 0;
			Delete.push(*Iter);
			Iter = Person.erase(Iter);
			Count++;

			continue;
		}

		Iter++;
		Count++;
	}

	std::cout << "<";
	while (Delete.size() > 0)
	{
		int CurIndex = Delete.front();
		Delete.pop();

		std::cout << CurIndex;

		if (Delete.size() > 0)
		{
			std::cout << ", ";
		}
	}

	std::cout << ">";

	return 0;
}

다른 사람들과 비교했을 때, 썩 빠른 코드는 아니라서 조금 더 고민을 해볼 필요가 있을 것 같다.