백준 28281번 (선물, C++) [BAEKJOON]

목차 테이블

선물

https://www.acmicpc.net/problem/28281

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초1024 MB80256052772.490%

문제

 N일 뒤는 동원이의 생일이다. 축하해 주자!

준원이는 동원이에게 생일 선물로 양말을 2X개 선물하려 한다. 양말은 시장에서 살 것이다.

연속한 이틀에 걸쳐서, 준원이는 매일 시장에서 양말을 X개씩 사서 트럭에 담아올 것이다.

시장에서 양말의 가격은 날마다 다를 수 있다.

오늘부터 i번째 날에, 양말은 하나에 Ai원이다.

동원이의 생일까지 N일 남았다!

남은 N일 가운데 연속한 이틀에 걸쳐 양말 2X개를 사는 데 드는 최소 비용은?

입력

첫째 줄에 N과 X가 공백을 사이에 두고 주어진다.

둘째 줄에 N일간 양말의 가격 A1, A2 … AN이 공백을 사이에 두고 주어진다.

출력

연속한 이틀에 걸쳐 하루에 양말을 X개씩 구매하는 방법으로,

양말 X개를 사는 데 드는 최소 비용을 출력한다.

제한

  •  2 ≤ N ≤ 100000
  •  1 ≤ X ≤ 1000000
  •  1 ≤ Ai ≤ 1000 (1≤ i ≤ N)

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

54

1번째 날과 2번째 날에 양말을 각각 10개씩 사면 총 9 × 10 + 2 × 10 = 110원이 든다.

2번째 날과 3번째 날에 양말을 각각 10개씩 사면 총 2 × 10 + 5 × 10 = 70원이 든다.

3번째 날과 4번째 날에 양말을 각각 10개씩 사면 총 5 × 10 + 7 × 10 = 120원이 든다.

4번째 날과 5번째 날에 양말을 각각 10개씩 사면 총 7 × 10 + 6 × 10 = 130원이 든다.

가능한 위 네 가지 경우 중 비용이 최소가 되는 경우는 2번째 날과 3번째 날에 양말을 사는 경우이며, 최소 비용은 70원이다.

예제 입력 2

7 142857
22 35 9 12 25 19 10

예제 출력 2

2999997

예제 2에서는 3번째 날과 4번째 날에 양말을 살 때 최소 비용으로 양말을 살 수 있다.

출처

University > 연세대학교 미래캠퍼스 > 강원도 대학생 코딩 경진대회 A번


통과된 코드

#include <iostream>
using namespace std;
int _N, _Res, _X, _Arr[3] = { 1000, 1000, 0};
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N >> _X;
	_Res = INT32_MAX;
	for (int i = 0; i < _N; i++) {
		cin >> _Arr[2];
		_Arr[0] = _Arr[1];
		_Arr[1] = _Arr[2];
		_Res = min(_Res, (_Arr[0] + _Arr[1]) * _X);
	}
	cout << _Res;
	return 0;
}

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

위로 스크롤