prac 120

[javelinsman]

Practice 1202 #1 요세푸스 문제(Josephuse Problem)

이 문제에서는 유명한 요세푸스 문제를 풀어보겠습니다. n명의 사람들이 동그랗게 둘러 앉아 있습니다. 각 사람에게는 1, 2, 3, ..., n의 번호가 부여되어 있습니다. 또한 n보다 작은 자연수 k가 주어집니다. 게임이 시작하면 1번 사람이 바통을 들고 있다가 k번째 옆 사람에게 넘겨줍니다. 바통을 받은 사람은 게임에서 빠지고, 그 옆 사람이 바통을 이어받은 뒤 또 다시 k번째 옆 사람에게 넘겨줍니다. 이런 식으로 마지막 1명이 남을 때까지 계속됩니다.

예를 들어, n=5이고 k=3이라면 다음과 같이 진행됩니다. (굵은 글씨는 바통을 가지고 있다는 뜻입니다)

1. 1 2 3 4 5 → 1 2 3 4 5 → 1 2 3 4 5 → 1 2 3 4 5 → 4 out → 1 2 3 5
2. 1 2 3 5 → 1 2 3 5 → 1 2 3 5 → 1 2 3 5 → 3 out → 1 2 5
3. 1 2 5 → 1 2 5 → 1 2 5 → 1 2 5 → 5 out → 1 2
4. 1 2 → 1 2 → 1 2 → 1 2 → 2 out → 1

따라서, n=5이고 k=3일때 마지막으로 남는 사람은 1입니다.

Queue (혹은 Deque)를 사용하여 요세푸스 게임을 시뮬레이션하는 프로그램을 작성하세요. 주어진 n과 k에 대해 가장 마지막으로 남는 사람의 번호를 출력하면 됩니다. list를 사용해서 .pop(0)과 같이 시간이 오래 걸리는 메소드를 사용하면 시간 초과가 될 수 있습니다.

Input
1 이상의 자연수 n과 k가 띄어쓰기를 기준으로 구분되어 주어집니다. k는 항상 n보다 작습니다.

5 3

Output

1

[javelinsman]

Practice 1202 #2 재고 준비하기

당신은 슈퍼마켓을 운영하고 있습니다. 지금은 내일의 매장 오픈을 준비하기 위해 발주(=물건을 주문)를 할 시간입니다. 발주를 하는 방법은 다음과 같습니다.

1. 어제 팔린 항목들의 목록을 보고, 가장 많이 팔린 A개의 항목을 팔린 개수만큼 주문합니다.
   • 동률(tie)이 있다면 모두 포함시킵니다. 즉, A번째로 많이 팔린 물건과 동일한 개수만큼 팔린 다른 물건들이 있다면 해당하는 물건들도 모두 포함시켜서, 팔린 개수만큼 주문합니다.
   • 남은 물건의 수보다 A가 더 크다면 남은 물건의 수 만큼 주문합니다.
2. 위 1번 과정에서 주문되지 않은 물건들 중, 가장 적게 팔린 B개의 물건은 아예 주문하지 않습니다.
   • 마찬가지로 동률이 있다면 모두 포함시킵니다. 즉, B번째로 적게 팔린 물건과 동일한 개수만큼 팔린 다른 물건들이 있다면 해당하는 물건들도 모두 포함시켜서, 아무것도 주문하지 않습니다.
   • 남은 물건의 수보다 B가 더 크다면 남은 물건의 수 만큼 주문합니다.
3. 위의 두 가지 경우에 속하지 않는 물건은 모두 C개씩 주문합니다.

당신은 위와 같은 방법으로 재고를 구축한 뒤 오늘의 장사를 시작합니다. (편의상 어제 팔고 남은 재고는 없다고 가정합니다. ) 오늘의 주문 목록이 들어올 때, (1) 주문이 모두 끝나고 남은 재고가 어떻게 되는지, 그리고 (2) 재고가 없어 팔지 못한 항목은 없는지를 계산하세요.

Input

• 입력의 첫 줄에는 A B C가 띄어쓰기로 구분되어 주어집니다. A B C는 모두 0 이상의 정수입니다.
• 입력의 두 번째 줄에는 품목들이 띄어쓰기로 구분되어 주어집니다. 주어지는 품목들은 모두 서로 다릅니다.
• 입력의 세 번째 줄에는 어제 주문 된 품목들이 띄어쓰기로 구분되어 주어집니다.
• 입력의 네 번째 줄에는 오늘 주문 된 품목들이 띄어쓰기로 구분되어 주어집니다.

1 1 1
apple banana pineapple orange
apple apple apple banana pineapple banana
apple orange orange banana banana

Explanation

위의 입력을 해석하면 다음과 같습니다.

• apple, banana, pineapple, orange의 4개 품목이 있습니다.
• 어제는 apple이 3개, banana가 2개, pineapple이 1개 팔렸습니다.
• 오늘의 재고를 주문합니다.
  • 가장 많이 팔린 A=1개의 품목, 즉 apple을 팔린 개수만큼 3개 삽니다.
  • 가장 적게 팔린 B=1개의 품목, 즉 orange를 아예 주문하지 않습니다.
  • 나머지인 banana와 pineapple을 C=1개씩 주문합니다.
  • 따라서 오늘의 재고는 apple 3개, banana 1개, pineapple 1개입니다.
• 오늘은 apple 1개, orange 2개, banana 2개를 주문 받았습니다.
  • apple은 3개 중 1개를 팔고 2개가 남았습니다.
  • orange는 재고에 없기 때문에 2개를 팔지 못했습니다.
  • banana는 재고에 있던 1개를 팔고, 1개는 재고가 부족해서 팔지 못했습니다.
  • 따라서 남은 재고는 apple 2개, banana 0개, pineapple 1개, orange 0개입니다.
  • 재고가 팔지 못한 개수는 apple 0개, banana 1개, pineapple 0개, orange 2개입니다.

Output

첫 줄에는 남은 재고를, 두 번째 줄에는 재고가 없어 팔지 못한 개수를 각각 한 줄에 출력합니다.
순서는 input에서 주어진 품목의 순서(=apple, banana, pineapple, orange)와 동일해야 합니다.

2 0 1 0
0 1 0 2