[Codingame] ROLLER COASTER(롤러코스터 대기열 시뮬레이션 - Circular queue, Dynamic programming
문제 간략 설명: 놀이공원 분석 센터에 새로 배치된 당신은 놀이기구의 수익을 예측하는 임무를 맡게 됩니다. 가장 먼저 롤러코스터를 살펴봅니다.
[사진]
[Rules_규칙]
목표: 하루 동안 롤러코스터가 벌어들일 수익을 예측합니다.
규칙:
놀이공원의 사람들은 롤러코스터를 매우 좋아해서 롤러코스터에서 내리자마자 다른 기구에는 관심도 없이 다시 롤러코스터를 타려고 줄을 섭니다.
■롤러코스터의 탑승 규칙은 다음과 같습니다.
- 롤러코스터 앞에 차례대로 줄을 서고, 줄을 선 순서대로 탑승합니다.
- 단체 손님은 모두 함께 탑승하기를 원합니다. 같은 그룹에 속한 손님들은 여러 대에 나눠 탑승할 수 없습니다.
- 지정된 좌석보다 초과한 인원을 태울 수 없습니다.
- 단체 손님을 모두 태우기에 좌석이 부족한 경우에는 롤러코스터에 탑승시키지 않고 그냥 출발합니다.
탑승하지 못한 손님은 다음 차에 탑승하도록 합니다.
그러므로 롤러코스터에서 일부 좌석이 빈 채로 운행될 수 있습니다.
- 탑승객은 롤러코스터에서 내리자마자 대기열의 맨 뒤에 다시 차례대로 줄을 섭니다.
■롤러코스터의 운행 규칙은 다음과 같습니다.
- 롤러코스터는 한 번에 L명까지 승객을 태울 수 있습니다.
- 롤러코스터는 하루에 C번 운행합니다.
- 대기열에는 N개의 손님 그룹이 있습니다. 그룹은 개인이거나 단체일 수 있습니다.
- 각 그룹에는 Pi 명의 사람이 있습니다.
- 롤러코스터의 이용 요금은 1명당 1원입니다.
- 탑승정원보다 그룹의 인원이 많은 경우는 고려하지 않아도 됩니다.
- L, C, N, Pi는 입력 값으로 제공됩니다.
[예시]
다음 경우를 예를 들어 보겠습니다.
L=3(탑승 정원), C=3(운행 횟수), N=4(그룹의 개수)이 있고 Pi(그룹의 인원수)=[3, 1, 1, 2]라고 합시다.
롤러코스터는 하루에 3번(C) 운행합니다.
- 첫 번째 운행: 롤러코스터의 탑승 정원(L)은 3명이고 첫 번째 그룹은 3명입니다.
첫 번째 그룹을 태우고 운행을 시작합니다. 3명을 태웠으므로 매출은 3원입니다.
운행을 마친 손님은 대기열의 맨 뒤에 줄을 섭니다.
대기열은 [1, 1, 2, 3]이 됩니다.
- 두 번째 운행: 대기열에 각각 1명씩 두 그룹이 있습니다.
두 그룹을 태우면 한 자리만 남아서 그 뒤의 그룹 2명을 모두 태울 수 없습니다.
그러므로 2명만 태우고 운행을 시작합니다. 매출은 2원입니다. 운행을 마친 승객은 다시 대기열의 맨 뒤에 줄을 섭니다.
대기열은 [2, 3, 1, 1]이 됩니다.
-세 번째 운행: 첫 번째 그룹 2명만이 롤러코스터에 탑승할 수 있습니다.
앞선 운행과 마찬가지로 한 자리는 비운 채 운행합니다. 매출은 2원입니다.
3번의 운행을 모두 마쳤고 총매출은 3 + 2 + 2 = 7원입니다.
[풀이 영상]
[문제]
https://www.codingame.com/training/hard/roller-coaster
Practice Dynamic programming and Simulation with the exercise "Roller Coaster"
Want to practice Dynamic programming and simulation? Try to solve the coding challenge "Roller Coaster".
www.codingame.com
[난이도]
[학습 개념]
[풀이]
1. 문제를 얼핏 보면 솔직히 쉬운 문제 같아 보입니다. 하지만 이 문제의 난이도는 Hard입니다. 생각대로 하면 6개의 테스트 케이스 중 3번까지는 바로 풀리지만 그 이후의 문제들은 안 풀립니다. 왜 그런지 이제 풀이를 보면서 알아보겠습니다.
2. 이 문제를 요약하면 대기열에 있는 손님들을 롤러코스터에 총 몇 명 태울 수 있는지 계산하는 문제입니다.
3. 대기열 순서대로 승객을 롤러코스터에 태우고 운행을 시작합니다. 운행이 종료되면 탑승했던 승객은 롤러코스터에서 내려 대기열의 맨 뒤에 다시 섭니다.
4. 대기열의 맨 앞에서 손님이 빠져나오고 맨 뒤에서 줄을 서는 것을 보면 이 문제는 큐를 사용해야 한다는 것을 직감적으로 알 수 있습니다.
5. 이런 생각을 가지고 제가 직접 처음에 짠 코드를 보여드리겠습니다.
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// 입력 받기
string[] inputs = Console.ReadLine().Split(' ');
int L = int.Parse(inputs[0]); // 좌석의 총 수
int C = int.Parse(inputs[1]); // 운행 횟수
int N = int.Parse(inputs[2]); // 그룹의 수
// 그룹별 인원수 입력 받기
Queue<int> pi = new Queue<int>();
for (int i = 0; i < N; i++)
{
pi.Enqueue(int.Parse(Console.ReadLine()));
}
int totalRevenue = 0; // 총 매출
Queue<int> peopleOnRide = new Queue<int>(); // 탑승한 사람들을 저장하는 큐
// 운행 횟수만큼 반복
for (int i = 0; i < C; i++)
{
int numPassengers = 0; // 현재 운행에서 탑승한 인원 수
// 운행 가능한 인원 수와 좌석의 총 수를 고려하여 탑승 가능한 그룹을 큐에서 꺼내기
while (pi.Count > 0 && numPassengers + pi.Peek() <= L)
{
int group = pi.Dequeue(); // 큐에서 그룹 인원수 꺼내기
peopleOnRide.Enqueue(group); // 탑승한 사람들 큐에 추가
numPassengers += group; // 현재 운행에서 탑승한 인원 수 증가
}
totalRevenue += numPassengers; // 현재 운행에서의 매출 총합에 추가
// 탑승한 사람들을 다시 큐에 넣어 준다 (한 바퀴를 돌려서 처음으로 돌아옴)
foreach (int p in peopleOnRide)
{
pi.Enqueue(p);
}
}
// 총 매출 출력
Console.WriteLine(totalRevenue);
}
}그러고 테스트 케이스를 해보면 이런 결과가 나옵니다.
왜 이런 결과가 나오는지 테스트 케이스의 입력값을 한 번 보겠습니다.
문제가 무엇일까요?
바로 탑승한 사람들이 다 타고 다시 대기열에 보낼 때 탑승한 사람들을 내보내지 않고 대기열에 보내는 문제입니다.
사람이 두배로 불어나서 대기열에 붙게 됩니다. ㄷㄷ...
// 탑승한 사람들을 다시 큐에 넣어 준다 (한 바퀴를 돌려서 처음으로 돌아옴)
foreach (int p in peopleOnRide)
{
pi.Enqueue(p);
}
이 부분을 아래처럼 바꿔서 해결했습니다.
// peopleOnRide 큐의 원소를 모두 제거하고 pi 큐에 추가
while (peopleOnRide.Count > 0)
{
pi.Enqueue(peopleOnRide.Dequeue());
}이제 다시 풀어보면 4번은 풀어졌습니다. 하지만 5번부터 다시 막힙니다.
여기서 문제를 보면 2의 32승입니다. 정답이 49억원입니다. 헉 하루에 매출이 거의 50억입니다!
이런 큰 값은 int로는 담을 수 없습니다.
이렇게 알면 쉽습니다. 더 큰 값도 담을 수 있게 자릿수에 구애 받지 않게 해 주는 임의정밀도(arbitrary precision) 라이브러리를 이용해보겠습니다. C#,Java BigInteger와 BigDecimal 클래스를 사용합니다.
BigInteger totalRevenue = 0;이렇게 하면 6번 빼고 다 풀립니다.
하지만 이 문제가 Hard인 이유가 6번에 있습니다.
▶ 빅데이터를 다룰 때의 최적화 문제
입력값과 결과값을 보면 진짜 현실적인 숫자가 아닙니다. 하지만 테스트에서는 허용하는 범위입니다.
앞에서 작성했던 코드로 결과를 계산할 때까지 기다리려면 얼마나 걸릴지 짐작조차 되지 않습니다.
더 효율적인 방법을 찾아야 합니다.
문제 분석
먼저 승객이 롤러코스터에 타고 내리는 상황을 살펴보겠습니다.
| 2 | • • • | 998 | 999 | 0 | 1 |
0번 그룹이 롤러코스터 운행을 마치고 나오면 대기열의 맨 뒤에 다시 줄을 섭니다.
이를 큐로 표현하면 큐의 맨 앞에서 빠져나온 데이터를 맨 뒤에 추가하는 것과 같습니다.
1번 그룹도 마찬가지로 맨 앞에서 나오고 맨 뒤로 이동합니다.
이는 흡사 큐의 맨 앞과 맨 뒤가 연결되어 있고 탑승 순서가 0번부터 차례대로 999번 지나 다시 0번으로 되돌아가는 구조와 같습니다.
이를테면 원형으로 되어 있는 대기열의 순서대로 탑승하는 것처럼 보입니다.
이렇게 큐가 원형으로 되어 있고 순서가 항상 고정되어 있다면 대기열에서 요소를 뺏다 할 것이 아니라 탑승할 그룹의 위치를 지정하고 매 탑승마다 탑승 순번만 하나씩 이동하면 될 것입니다.
그리고 그 순번이 끝 번에 도달하면 다시 0으로 되돌아가게 하는 것입니다.
매번 요소를 추가하고 삭제하지 않으니 성능 개선에 많은 도움이 될 것입니다.
사실은 C#에서 Queue<T> 클래스는 내부적으로 원형 큐(circular queue) 방식으로 구현됩니다.
원형 큐는 디큐된 요소의 공간을 재사용하여 효율적인 인큐(Enqueue)와 디큐(Dequeue) 작업을 수행합니다.
하지만 Queue<T> 클래스는 내부적으로 원형 큐를 사용하고 있지만,
직접적으로 인덱스를 이용하여 큐의 요소에 접근하는 것은 제한됩니다.
그리고 원형 큐를 구현해보고 인덱스를 사용할 수 있게 직접 만들어서 사용해 보는 것도 중요하다고 생각합니다.아래 코드는 그렇게 수정한 코드입니다.
namespace RollerCoaster
{
class CircularQueue<T>
{
private T[] queue; // 큐의 요소를 저장하는 배열
private int front; // 큐의 첫 번째 요소를 가리키는 인덱스
private int rear; // 큐의 마지막 요소를 가리키는 인덱스
private int count; // 큐의 현재 요소 개수
public CircularQueue(List<T> initialItems)
{
queue = new T[initialItems.Count]; // 초기 요소 개수에 맞게 배열 크기 설정
front = 0; // 초기화: front를 0으로 설정
rear = initialItems.Count - 1; // 초기화: rear를 마지막 요소 위치로 설정
count = initialItems.Count; // 초기화: 요소 개수 설정
for (int i = 0; i < initialItems.Count; i++)
{
queue[i] = initialItems[i]; // 초기 요소를 배열에 복사
}
}
public T this[int index]
{
get
{
if (index < 0 || index >= count)
{
throw new IndexOutOfRangeException("Index is out of range.");
}
int actualIndex = (front + index) % queue.Length; // 실제 인덱스 계산
return queue[actualIndex]; // 해당 인덱스의 요소 반환
}
set
{
if (index < 0 || index >= count)
{
throw new IndexOutOfRangeException("Index is out of range.");
}
int actualIndex = (front + index) % queue.Length; // 실제 인덱스 계산
queue[actualIndex] = value; // 해당 인덱스의 요소에 값 설정
}
}
public void Enqueue(T item)
{
if (count == queue.Length)
{
Console.Error.WriteLine("Queue is full. Cannot enqueue.");
return;
}
rear = (rear + 1) % queue.Length; // rear 위치를 계산하여 다음 빈 공간을 찾음
queue[rear] = item; // rear 위치에 새로운 원소 추가
count++; // 큐의 원소 개수 증가
}
public T Dequeue()
{
if (count == 0)
{
Console.Error.WriteLine("Queue is empty. Cannot dequeue.");
return default(T); // 예외 처리를 위해 기본값 반환
}
T item = queue[front]; // front 위치의 원소를 가져옴
front = (front + 1) % queue.Length; // front 위치를 계산하여 다음 원소로 이동
count--; // 큐의 원소 개수 감소
return item; // 제거된 원소 반환
}
public T Peek()
{
if (count == 0)
{
Console.Error.WriteLine("Queue is empty. Cannot peek.");
return default(T); // 예외 처리를 위해 기본값 반환
}
return queue[front]; // front 위치의 원소 반환 (제거하지 않고 확인만 함)
}
public bool IsEmpty()
{
return count == 0; // 원소 개수가 0인지 확인
}
public bool IsFull()
{
return count == queue.Length; // 원소 개수가 큐의 크기와 같은지 확인
}
}
class RollerCoaster
{
// 롤러코스터의 매출을 계산하는 함수입니다.
// L: 좌석의 총 수
// C: 운행 횟수
// N: 그룹의 수
// groups: 그룹별 인원수 리스트
static BigInteger CalculateRevenue(int L, int C, int N, List<int> groups)
{
CircularQueue<int> circularQueue = new CircularQueue<int>(groups);
BigInteger totalRevenue = new BigInteger(); // 총소득
int nextIndex = 0; // 다음 탐승할 그룹의 위치를 지정합니다.
for (int ride = 0; ride < C; ride++)
{
int num_passengers = 0;
while (num_passengers + circularQueue[nextIndex] <= L)
{
num_passengers += circularQueue[nextIndex];
nextIndex = (nextIndex + 1) % N;
}
totalRevenue += num_passengers;
}
return totalRevenue;
}
static void Main(string[] args)
{
string[] inputs = Console.ReadLine().Split(' ');
int L = int.Parse(inputs[0]);
int C = int.Parse(inputs[1]);
int N = int.Parse(inputs[2]);
List<int> pi = new List<int>();
for (int i = 0; i < N; i++)
{
pi.Add(int.Parse(Console.ReadLine()));
}
BigInteger totalEarnings = CalculateRevenue(L, C, N, pi);
Console.WriteLine(totalEarnings);
}
}
}이전에 작성했던 코드보다 많이 좋아졌습니다. 하지만 변경된 코드에는 버그가 하나 있습니다.
예를 들어 롤러코스터의 정원 10명, 손님 그룹 2개, 각 그룹에는 2명씩 있는 경우를 생각해 봅시다.
첫 번째 그룹과 두 번째 그룹을 모두 태운 후 인덱스는 전체 그룹의 개수와 같은 2가 되어 다시 0이 되었습니다.
롤러코스터는 아직 6개의 빈 좌석이남아 있기 때문에 승객을 더 태울 수 있습니다.
다음 인덱스인 0번 그룹의 손님을 더 태워야 합니다. 잠깐! 0번 그룹은 이미 탑승했는데, 어떻게 또 태우죠?
큐 방식으로 코드를 작성했을 때는 탑승한 승객을 배열에서 빼기 때문에 대기열에
손님이 남아 있는지 확인하기 쉬웠습니다.
하지만 인덱스로 변경하면서 배열을 비우지 않으므로 확인하기 어려워졌습니다.
인덱스 방식에서 대기열을 확인하려면 롤러코스터를 맨 처음 탑승했던 그룹의 인덱스를 저장해 두고, 그 인덱스가 한 바퀴 돌았는지 확인하면 됩니다.
int beginIndex = 0; // 맨 처음 탑승을 시작한 인덱스의 위치를 저장
while (num_passengers + circularQueue[nextIndex] <= L)
{
num_passengers += circularQueue[nextIndex];
nextIndex = (nextIndex + 1) % N;
if (nextIndex == beginIndex) // 처음 탑승했던 지점과 만나면 빠져나옴
{
break;
}
}아니면 대기열의 총인원을 합산해서 롤러코스터 정원보다 적은 지 비교하면 한 번에 모든 승객을 태우고 계속 반복 운행하면 되기 때문에 인원 계산이 매우 간단해집니다.
int totalPassengers = groups.Sum(); // 전체 대기자
if (totalPassengers <= L) // 좌석이 전체 대기자보다 같거나 많으면 하루 운행 횟수를 곱하여 하루 매출액을 바로 구할 수 있다.
{
return totalRevenue = totalPassengers * C;
}
else
{
int nextIndex = 0; // 다음 탐승할 그룹의 위치를 지정합니다.
for (int ride = 0; ride < C; ride++)
{
int num_passengers = 0;
while (num_passengers + circularQueue[nextIndex] <= L)
{
num_passengers += circularQueue[nextIndex];
nextIndex = (nextIndex + 1) % N;
}
totalRevenue += num_passengers;
}
}이렇게 하고 다시 테스트를 해보겠습니다.
아직도 시간 안에 출력이 안됩니다.
그러면 여기서 더 뭐를 해야 할까요?
이 게임의 핵심은 탑승 횟수가 매우 많아 승객이 여러 번 탑승한다는 것입니다.
손님의 탑승 패턴에서 어떤 실마리를 찾아야 합니다.
대기열의 손님이 수백, 수천번 반복해서 탑승하다 보면 어느 순간에 같은 패턴이 반복되는 경우를 발견하게 됩니다.
왜냐하면 비록 서로 다른 지점에서 승객을 태우기 시작했다 하더라도 다음 그룹의 인원을 모두 태우지 못한다면 같은 지점에서 탑승이 마감되는 경우가 있기 때문입니다.
이러한 반복 패턴을 발견하면 탑승 인원을 계산할 때, 이전에 계산한 값을 재사용하여 효율을 향상할 수 있습니다.
이와 같이 문제 해결 중간 과정에서 얻은 값을 재사용하여 전체 문제의 계산을 빠르게 수행하도록 코드를 작성하는 방법을 동적 프로그래밍이라고 합니다.
▶동적 프로그래밍
동적 프로그래밍(Dynamic Programming)은 큰 문제를 작은 하위 문제로 분할하여 효율적으로 해결하는 알고리즘 설계 기법입니다. 이는 중복 계산을 피하고 계산 결과를 저장하여 필요할 때 재사용함으로써 계산 속도를 향상합니다.
파보나치 수열은 대표적인 동적 프로그래밍의 예입니다.
파보나치 수열은 다음과 같이 재귀 함수를 이용해서 작성하면 다음과 같습니다.
class Fibonacci
{
static long FibonacciRecursive(int n)
{
// 1번 항과 2번 항은 1을 반환합니다.
if (n <= 2)
return 1;
//앞 두 항의 합을 반환합니다.
return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
}이해하기 쉽고 직관적이고 이보다 더 좋은 예를 찾기 힘들 것입니다.
하지만 심각한 단점이 있습니다. 바로 항이 커질수록 계산 속도가 기하급수적으로 느려진다는 점입니다.
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \
F(2) F(1)5번째 까지는 쉽습니다.
하지만 94번째 항을 보시면
F(94)
/ \
F(93) F(92)
/ \ / \
F(92) F(91) F(91) F(90)
/ \ / \ / \ / \
F(91) F(90) F(90) F(89) F(90) F(89) F(89) F(88)F(94)까지의 재귀 함수를 사용하여 호출해야 하는 부분 함수의 총횟수는 19,308,454,815(2의 34승) 번입니다.
저 다이어그램에서 F(94)를 계산하기 위해 F(90)이 4번 호출되지만 F(90)을 계산하기 위해 호출되는 부분 함수는 셀 수 없을 정도로 많습니다.
다이어그램에서 보듯이 F(90)은 겨우 4번 호출되지만 한 번 한 번의 계산 시간이 매우 오래 걸립니다.
이를 줄일 방법이 필요합니다.
아시다시피 F(90)은 언제나 같은 값을 반환합니다.
즉, 한 번만 계산하고 이를 재사용하면 되는데 매번 계산하는 것은 매우 비효율적입니다.
수열의 각 항을 계산한 후 그 값을 어딘가에 저장했다가 다음에 값은 항을 계산할 때 저장했던 값을 사용하면 어떨까요?
저장된 값을 꺼내오는 것은 새로 계산하는 것보다 빠릅니다.
그렇게 수정된 코드입니다.
class Fibonacci
{
static Dictionary<int, long> memo = new Dictionary<int, long>();
static long FibonacciDP(int n)
{
if (memo.ContainsKey(n))
return memo[n];
// 1번 항과 2번 항은 1을 반환합니다.
if (n <= 2)
return 1;
long fib = FibonacciDP(n - 1) + FibonacciDP(n - 2);
memo[n] = fib;
return fib;
}
}재귀 피보나치와 동적 프로그래밍 피보나치에 값을 45를 넣고 돌렸을 때의 출력까지의 시간을 비교해 보겠습니다.
시간 차이가 엄청 차이 나고 이런 차이는 값이 클수록 더욱 벌어지게 될 것입니다.
[소스 코드]
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
namespace RollerCoaster
{
class CircularQueue<T>
{
private T[] queue; // 큐의 요소를 저장하는 배열
private int front; // 큐의 첫 번째 요소를 가리키는 인덱스
private int rear; // 큐의 마지막 요소를 가리키는 인덱스
private int count; // 큐의 현재 요소 개수
public CircularQueue(List<T> initialItems)
{
queue = new T[initialItems.Count]; // 초기 요소 개수에 맞게 배열 크기 설정
front = 0; // 초기화: front를 0으로 설정
rear = initialItems.Count - 1; // 초기화: rear를 마지막 요소 위치로 설정
count = initialItems.Count; // 초기화: 요소 개수 설정
for (int i = 0; i < initialItems.Count; i++)
{
queue[i] = initialItems[i]; // 초기 요소를 배열에 복사
}
}
public T this[int index]
{
get
{
if (index < 0 || index >= count)
{
throw new IndexOutOfRangeException("Index is out of range.");
}
int actualIndex = (front + index) % queue.Length; // 실제 인덱스 계산
return queue[actualIndex]; // 해당 인덱스의 요소 반환
}
set
{
if (index < 0 || index >= count)
{
throw new IndexOutOfRangeException("Index is out of range.");
}
int actualIndex = (front + index) % queue.Length; // 실제 인덱스 계산
queue[actualIndex] = value; // 해당 인덱스의 요소에 값 설정
}
}
public void Enqueue(T item)
{
if (count == queue.Length)
{
Console.Error.WriteLine("Queue is full. Cannot enqueue.");
return;
}
rear = (rear + 1) % queue.Length; // rear 위치를 계산하여 다음 빈 공간을 찾음
queue[rear] = item; // rear 위치에 새로운 원소 추가
count++; // 큐의 원소 개수 증가
}
public T Dequeue()
{
if (count == 0)
{
Console.Error.WriteLine("Queue is empty. Cannot dequeue.");
return default(T); // 예외 처리를 위해 기본값 반환
}
T item = queue[front]; // front 위치의 원소를 가져옴
front = (front + 1) % queue.Length; // front 위치를 계산하여 다음 원소로 이동
count--; // 큐의 원소 개수 감소
return item; // 제거된 원소 반환
}
public T Peek()
{
if (count == 0)
{
Console.Error.WriteLine("Queue is empty. Cannot peek.");
return default(T); // 예외 처리를 위해 기본값 반환
}
return queue[front]; // front 위치의 원소 반환 (제거하지 않고 확인만 함)
}
public bool IsEmpty()
{
return count == 0; // 원소 개수가 0인지 확인
}
public bool IsFull()
{
return count == queue.Length; // 원소 개수가 큐의 크기와 같은지 확인
}
}
class RollerCoaster
{
// 롤러코스터의 매출을 계산하는 함수입니다.
// L: 좌석의 총 수
// C: 운행 횟수
// N: 그룹의 수
// groups: 그룹별 인원수 리스트
static BigInteger CalculateRevenue(int L, int C, int N, List<int> groups)
{
CircularQueue<int> circularQueue = new CircularQueue<int>(groups);
BigInteger totalRevenue = new BigInteger(); // 총소득
int totalPassengers = groups.Sum();
if (totalPassengers <= L) // 좌석이 전체 대기자보다 같거나 많으면 하루 운행 횟수를 곱하여 하루 매출액을 바로 구할 수 있다.
{
return totalRevenue = totalPassengers * C;
}
else
{
// 딕셔너리 키는 시작 인덱스로 하고 딕셔너리에 저장할 값은 탑승 인원과 탑승을 마치고 난 후의 인덱스가 됩니다.
// 다시 말해, 시작 인덱스만 알면 탑승 인원과 탑승을 끝마친 후의 인덱스를 알 수 있습니다.
Dictionary<int, Tuple<int, int>> rvenueHistory = new Dictionary<int, Tuple<int, int>>();
int nextIndex = 0; // 다음 탐승할 그룹의 위치를 지정합니다.
for (int ride = 0; ride < C; ride++)
{
int num_passengers = 0;
if (rvenueHistory.ContainsKey(nextIndex))
{
//인덱스가 딕셔너리에 있다면 바로 다음 운행 정보와 탑승 인원을 얻어옵니다.
(nextIndex, num_passengers) = rvenueHistory[nextIndex];
}
else
{
int beginIndex = nextIndex;
while (num_passengers + circularQueue[nextIndex] <= L)
{
num_passengers += circularQueue[nextIndex];
nextIndex = (nextIndex + 1) % N;
}
rvenueHistory[beginIndex] = Tuple.Create(nextIndex, num_passengers);
}
totalRevenue += num_passengers;
}
return totalRevenue;
}
}
static void Main(string[] args)
{
string[] inputs = Console.ReadLine().Split(' ');
int L = int.Parse(inputs[0]);
int C = int.Parse(inputs[1]);
int N = int.Parse(inputs[2]);
List<int> pi = new List<int>();
for (int i = 0; i < N; i++)
{
pi.Add(int.Parse(Console.ReadLine()));
}
BigInteger totalEarnings = CalculateRevenue(L, C, N, pi);
Console.WriteLine(totalEarnings);
}
}
}
[새롭게 알게 된 점]
1. 큐 내부 동작 과정이 실은 원형 큐 방식으로 동작하고 있다는 걸 알게 되었다.
2. 원형 큐를 구현해 보고 리스트로 초기화 할 수 있게 해보고 인덱스로 값을 가져오거나 수정할 수 있게 해 보면서
자료구조에 나를 맞추는 게 아닌 내가 원하는 결과물을 내기 위해 수정하면서 실력이 많이 늘었다
3. 동적 프로그래밍 최적화 기법을 통해 이때까지 많은 시간을 걸렸던 다른 결과물들에 적용해 보면 더 좋겠는데? 하고 생각이 들고 이번에 피보나치로 개념을 익히고 문제를 풀면서 사용해 보면서 최적화가 생각보다 많이 중요하다는 걸 알게 되었고 실력도 많이 향상되었다.