i can do ik!

BOJ 24511 queuestack

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 

그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1번, 2번, ... , N번의 자료구조(queue 혹은 stack)가 나열되어있으며, 

각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다.

이전에 삽입한 결과는 남아 있다. (예제 1 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 1024 MB (추가 메모리 없음)

입력

출력

수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

예제 입력 1

4
0 1 1 0
1 2 3 4
3
2 4 7

각 상태에 대한 큐스택 내부를 표현하면 다음과 같다.

• 초기 상태 : [1, 2, 3, 4]
• 첫 번째 원소 삽입 : [2, 2, 3, 1]
• 두 번째 원소 삽입 : [4, 2, 3, 2]
• 세 번째 원소 삽입 : [7, 2, 3, 4]

예제 출력 1

4 1 2

예제 입력 2

5
1 1 1 1 1
1 2 3 4 5
3
1 3 5

예제 입력 2

1 3 5

풀이

import sys
from collections import deque

input = sys.stdin.readline
queue = deque()
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

for i in range(n):
	if a[i] == 0:
		queue.appendleft(b[i])
m = int(input())
arr = list(map(int, input().split()))

for i in arr:
	queue.append(i)
	print(queue.popleft(), end=" ")

BOJ 12873 기념품

문제

백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다.

하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다.

따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다.

게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다.

다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다.

이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다.

게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 

각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 

그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사람에게 이동하며 "둘"을 외친다. 

이 과정은 t단계인 경우에 t3을 외칠 때 까지 진행한다. 

예를 들어, 1단계에서는 1까지 외치며, 2단계에서는 8까지, 3단계에서는 27까지 외친다.

각 단계가 끝난 경우에, 백준이가 앞에 서 있는 사람은 게임에서 제외된다.(t단계인 경우에 t3을 외칠 때 앞에 있던 사람)

사람이 제거된 후에는 백준이는 시계 방향으로 다음 사람에게 이동한다.

1단계에서 백준이는 티셔츠 1번을 입고 있는 사람의 앞에 있다.

게임은 원에 한 명이 남을 때 까지 진행되며, 마지막 남은 사람이 기념품을 가져가게 된다.

참가자의 수 N이 주어졌을 때, 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 512 MB

입력

첫째 줄에 BOJ 캠프 참가자의 수 N (1 ≤ N ≤ 5,000)이 주어진다.

출력

첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.

예제 입력 1

3

예제 출력 1

2

예제 입력 2

6

예제 출력 2

6

예제 입력 3

10

예제 출력 3

8

풀이

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
queue = deque([i for i in range(1, n+1) ])
t =1

for i in range(n-1):
    num = (t**3) % len(queue)
    if num == 1:
        queue.popleft()
    else:    
        queue.rotate(-(num-1))            
        queue.popleft()
    t += 1

print(*queue)

BOJ 14713 앵무새

문제

자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 

그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데,

바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 

그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다.

1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 

그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 

그렇기 에 pps789는 앵무새 한 마리 대신 앵무새 N마리를 이용하여 자신의 발견을 기록하였으며, 이 앵무새들을 cseteram을 향해 날렸다.

한편 섬의 반대편에서 탐험을 계속하던 cseteram은 앵무새 N마리가 자신에게 날아와 각자 할 말을 하는 것을 보고 당황하였다. 

pps789가 긴 글을 전달하고 싶었던 것은 알아차렸지만, 

각각의 앵무새들이 말하는 것을 차례대로 기록하다 보니 원문이 무엇인지 알 수 없을 정도로 단어의 순서가 엉켜버린 것이다. 

대신 그는 관찰을 통해 몇 가지 규칙을 발견할 수 있었다.

1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다.
3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.

앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때 까지 단어를 받아적는다. 

pps789가 각각의 앵무새들에게 전달한 문장 Si와, cseteram이 받아 적은 문장 L이 주어진다. 

이때 문장 L이 위 규칙들을 이용하여 나올 수 있는 문장인지 판별하시오.

시간 제한 : 1 초
메모리 제한 : 512 MB

입력

첫 번째 줄에 앵무새의 수 N (1 ≤ N ≤ 100) 이 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 각 앵무새가 말한 문장 Si (1 ≤ i ≤ N) 가 주어지는데, 

각 문장을 이루는 단어는 스페이스 한 칸을 구분으로 하여 주어진다.

문장 Si를 이루는 단어의 수는 1개 이상 100개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성되어있다.

N + 2 번째 줄에는 cseteram이 받아 적은 문장 L이 주어진다. 

문장 L을 이루는 단어의 수는 1개 이상 10000개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성된다.

출력

문장 L이 가능한 문장이라면 Possible을, 불가능한 문장이라면 Impossible을 출력한다.

예제 입력 1

3
i want to see you
next week
good luck
i want next good luck week to see you

예제 출력 1

Possible

예제 입력 2

2
i found
an interesting cave
i found an cave interesting

예제 출력 2

Impossible

예제 입력 3

2
please
be careful
pen pineapple apple pen

예제 출력 3

Impossible

풀이

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
res = []

for i in range(n):
    queue = deque(input().split())
    res.append(queue)

sen = deque(input().split())

while sen:
    temp = sen.popleft()
    cnt = 0
    for i in res:
        if i[0] == temp:
            i.popleft()
            if not i:
                res.remove(i)
            cnt = 1
            break
    if cnt == 0:
        print('Impossible')
        exit(0)
if res:
    print('Impossible')
else:
    print('Possible')

BOJ 3078 좋은 친구

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.

??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 
    요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 
    말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 
    하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.

상근: 근데?

??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 
    근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 
    그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 
    그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 
    모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.

상근: 아? 근데 K는 어떻게 구해?

??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 
    말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.

상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 

좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

시간 제한 : 1 초
메모리 제헌 : 128 MB

입력

첫째 줄에 N과 K가 주어진다.

(3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 

이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

출력

첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.

예제 입력 1

4 2
IVA
IVO
ANA
TOM

예제 출력 1

5

예제 입력 2

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

예제 출력 2

2

풀이

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())
students = deque()
check = [0]*21
cnt = 0

for _ in range(n):
    if len(students) == k+1:
        check[len(students[0])] -= 1
        students.popleft()

    person = input().strip()
    num = len(person)
    cnt += check[num]
    check[num] += 1    
    students.append(person)

print(cnt)

BOJ 5464 주차장

문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다.

이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 

차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다.

만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 

만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 

만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 

만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다.

대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다.

주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 

또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 

오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

· 첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.
· 그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 
  그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.
· 그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다.
  차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 
  이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.
· 그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 
  양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 
  주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다.
  1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다.
  또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.
· 1 ≤ N ≤ 100 주차 공간의 수
· 1 ≤ M ≤ 2,000 차량의 수
· 1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금
· 1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다.

이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력 1

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

예제 출력 1

5300

예제 입력 2

2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

예제 출력 2

16200

힌트

차량 3이 주차 공간 1에 주차한다. 주차료는 300 * 2 = 600 이다.

차량 2가 주차 공간 2에 주차한다. 주차료는 100 * 3 = 300 이다.

차량 1이 차랑 3이 떠난 주차공간 1에 주차한다. 주차료는 200 * 2 = 400 이다.

차량 4가 마지막 남은 주차 공간 3에 주차한다. 주차료는 800 * 5 = 4,000 이다.

풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
spot = deque()
weight = deque()
wait = deque()
use = [0] * n
res = 0

for i in range(n):
    spot.append(int(input().strip()))
for i in range(m):
    weight.append(int(input().strip()))   
for i in range(m*2):
    car = int(input().strip())
    if car > 0:
        if 0 in use:
            for j in range(n):
                if use[j] == 0:
                    use[j] = car
                    break
        else:
            wait.append(car)
    else:
        a = use.index(-car)
        use[a] = 0
        res += weight[-car-1]*spot[a]
        if wait:
            use[a] = wait.popleft()

print(res)

BOJ 15828 Router

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 

이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 

마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 

네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 

그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 

즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 

이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 

라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 

만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 

그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자.

물론 하나의 라우터만 존재한다고 가정하며, 

우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 

그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 

어디로 보내고 이런 것들은 생각하지 말자.

시간 제한 : 1 초
메모리 제한 : 512 MB

입력

첫 줄에는 라우터 내부에 존재하는 버퍼의 크기를 나타내는 자연수 N이 주어진다.

둘째 줄부터 한 줄에 하나씩 라우터가 처리해야 할 정보가 주어진다.

모든 정보는 발생한 시간순으로 주어졌다고 가정한다.

양의 정수는 해당하는 번호의 패킷이 입력으로 들어왔다는 것을 의미하고, 

0은 라우터가 패킷 하나를 처리했다는 것을 의미한다. 

이때, 버퍼가 비어있을때는 0이 입력으로 들어오지 않는다. -1은 입력의 끝을 나타낸다.

출력

라우터에 남아있는 패킷을 앞에서부터 순서대로 공백으로 구분해서 출력하면 된다. 

만약 비어있을 경우 empty라고 출력한다.

Small(50점)

1 ≤ N ≤ 100,000

라우터가 처리해야 할 정보의 수는 N보다 작거나 같다.

Large(50점)

1 ≤ N ≤ 100,000

예제 입력 1

5
1
2
0
3
4
0
5
6
0
0
-1

예제 출력 1

5 6

예제 입력 2

1
1
2
3
4
5
6
7
-1

예제 출력 2

1

예제 입력 3

1
1
2
0
3
4
0
5
6
0
7
0
-1

예제 출력 3

empty

풀이

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
queue = deque()

while True :
    packet = input().strip()
    if packet == '-1':
        if len(queue) > 0:
            print(' '.join(queue))
        else : print('empty')
        break
    if packet == '0':
        queue.popleft()
    elif len(queue) < n :
        queue.append(packet)

BOJ 1158 요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 

이제 순서대로 K번째 사람을 제거한다. 

한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 

이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 

원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 

예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 256 MB

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

풀이

import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())
res = []
queue = deque(range(1, n+1))

for i in range(1, n+1):
    queue.rotate(-k+1)
    res.append(str(queue.popleft()))

print("<",", ".join(res)[:], ">", sep='')

BOJ 13335 트럭

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 

이 다리를 n 개의 트럭이 건너가려고 한다. 

트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 

다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 

다리의 길이는 w 단위길이(unit distance)이며, 

각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 

동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 

참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 

트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 

이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 

모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

시간 제한 : 1 초
메모리 제한 :  512 MB

입력

입력 데이터는 표준입력을 사용한다. 

입력은 두 줄로 이루어진다. 

입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, 

n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 

입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, 

ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

예제 입력 1

4 2 10
7 4 5 6

예제 출력 1

8

예제 입력 2

1 100 100
10

예제 출력 2

101

예제 입력 3

10 100 100
10 10 10 10 10 10 10 10 10 10

예제 출력 3

110

풀이

from collections import deque
import sys

input = sys.stdin.readline
n, w, L = map(int, input().split())
trucks = deque(list(map(int, input().split())))
queue = deque([0] * w)
cnt = 0
weight = 0

while queue:
  cnt += 1

  if trucks:
    weight -= queue.popleft()
    if weight + trucks[0] <= L:
      weight += trucks[0]
      queue.append(trucks.popleft())
    else:
      queue.append(0)
  else:
    queue.popleft()

print(cnt)