[Diamond IV] 라면 사기 (Large) - 18186

문제 링크

성능 요약

메모리: 9836 KB, 시간: 100 ms

분류

그리디 알고리즘

제출 일자

2024년 12월 7일 16:50:43

문제 설명

라면매니아 교준이네 집 주변에는 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가 사이에 공백을 두고 주어진다.

출력

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

문제 풀이

C++에서 int 대신 long long리턴 시 unsigned main으로 바꾸었다! (++새로운 지식)

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		long C = Long.parseLong(st.nextToken());
		long[] arr = new long[(int) (N+2)];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		long minCnt = 0;
		if(B<C) {
			for(int i=0; i<N; i++){
				minCnt += B * arr[i];
			}
		}
		else {
			for(int i=0; i<N; i++) {
				if(arr[i+1] > arr[i+2]) {
					// 2개짜리
					long cycle = Math.min(arr[i], arr[i+1] - arr[i+2]);
					for(int j=0; j<2; j++) {
						arr[i+j] -= cycle;
					}
					minCnt += (B+C)*cycle;
				
					// 3개짜리
					cycle = Math.min(arr[i], Math.min(arr[i+1], arr[i+2])); 
					for(int j=0; j<3; j++) {
						arr[i+j] -= cycle;
					}
					minCnt += (B+2*C)*cycle;
					
					cycle = arr[i];
					arr[i] -= cycle;
					minCnt += B*cycle;
				}
				else {
					long cycle = Math.min(arr[i], Math.min(arr[i+1], arr[i+2])); 
					for(int j=0; j<3; j++) {
						arr[i+j] -= cycle;
					}
					minCnt += (B+2*C)*cycle;
					
					cycle = Math.min(arr[i], arr[i+1]);
					for(int j=0; j<2; j++) {
						arr[i+j] -= cycle;
					}
					minCnt += (B+C)*cycle;
					
					cycle = arr[i];
					arr[i] -= cycle;
					minCnt += B*cycle;
				}
			}
		}
		
		bw.write(String.valueOf(minCnt));
		bw.flush();
		bw.close();
		br.close();
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N, B, C;
    cin >> N >> B >> C;
    vector<int> arr(N + 2);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int minCnt = 0;
    if (B < C) {
        for (int i = 0; i < N; i++) {
            minCnt += arr[i] * B;
        }
    } else {
        for (int i = 0; i < N; i++) {
            int cycle;
            if (arr[i + 1] > arr[i + 2]) {
                // 2묶음
                cycle = min(arr[i], arr[i + 1] - arr[i + 2]);
                for (int j = 0; j < 2; j++) {
                    arr[i + j] -= cycle;
                }
                minCnt += (B + C) * cycle;

                // 3묶음
                cycle = min(arr[i], min(arr[i + 1], arr[i + 2]));
                for (int j = 0; j < 3; j++) {
                    arr[i + j] -= cycle;
                }
                minCnt += (B + 2 * C) * cycle;

                // 1묶음
                cycle = arr[i];
                arr[i] -= cycle;
                minCnt += cycle * B;
            } else {
                // 3묶음
                cycle = min(arr[i], min(arr[i + 1], arr[i + 2]));
                for (int j = 0; j < 3; j++) {
                    arr[i + j] -= cycle;
                }
                minCnt += (B + 2 * C) * cycle;

                // 2묶음
                int cycle = min(arr[i], arr[i + 1]);
                for (int j = 0; j < 2; j++) {
                    arr[i + j] -= cycle;
                }
                minCnt += (B + C) * cycle;

                // 1묶음
                cycle = arr[i];
                arr[i] -= cycle;
                minCnt += cycle * B;
            }
        }
    }
    cout << minCnt << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}