BOJ: 18185, 18186

Posted on In

18185

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).
교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

  1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
  2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
  3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.
두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

출력

첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 3 ≤ N ≤ 104
  • 0 ≤ Ai ≤ 104 (1 ≤ i ≤ N)

18186

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).
교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

  1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 B원이 든다.
  2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 (B+C)원이 든다.
  3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 (B+2C)원이 든다.

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N과 두 자연수 B, C가 사이에 공백을 두고 주어진다.
두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

출력

첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 3 ≤ N ≤ 106
  • 1 ≤ B ≤ 106
  • 1 ≤ C ≤ 106
  • 0 ≤ Ai ≤ 106 (1 ≤ i ≤ N)

Solution

입력 구현

1
2
3
4
5
6
7
8
9
10
11
12
import sys
read = sys.stdin.readline

N, B, C = map(int, read().split())
l = list(map(int, read().split()))
l.append(0)
l.append(0)

a = B
b = B + C
c = B + 2 * C
cost = 0
  • 문제 18185는 문제 18186에서 B와 C의 값이 각각 3과 2로 지정된 경우이므로 문제 18186의 풀이만 작성
  • B와 C의 값을 입력받고 문제의 방법인 1. ~ 3.에 대한 비용을 변수 a, b, c에 할당

Greedy 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
if B <= C:
  print(sum(l) * a)
else:
  for i in range(N):
    if l[i + 1] > l[i + 2]:
      tmp = min(l[i], l[i + 1] - l[i + 2])
      l[i] -= tmp
      l[i + 1] -= tmp
      cost += b * tmp
  
      tmp = min(l[i], l[i + 1], l[i + 2])
      l[i] -= tmp
      l[i + 1] -= tmp
      l[i + 2] -= tmp
      cost += c * tmp
  
      tmp = l[i]
      l[i] -= tmp
      cost += a * tmp
    else:
      tmp = min(l[i], l[i + 1], l[i + 2])
      l[i] -= tmp
      l[i + 1] -= tmp
      l[i + 2] -= tmp
      cost += c * tmp
  
      tmp = min(l[i], l[i + 1])
      l[i] -= tmp
      l[i + 1] -= tmp
      cost += b * tmp
  
      tmp = l[i]
      l[i] -= tmp
      cost += a * tmp
  print(cost)
  • 변수 B가 변수 C보다 작거나 같은 경우 모든 라면 공장에서 각각 구매하는 것이 최소 금액이므로 sum(l)에 대해 a (방법 1.)를 곱하여 출력
  • 이 외의 경우에 최대한 동시에 (방법 3., 2.) 사는 것이 싸기 때문에 0부터 N - 1까지의 인덱스에 대해 Greedy 알고리즘을 적용