BOJ_18185_라면 사기 (Small) (Java, C++)

[Diamond V] 라면 사기 (Small) - 18185

문제 링크

성능 요약

메모리: 2180 KB, 시간: 0 ms

분류

그리디 알고리즘

제출 일자

2024년 12월 7일 16:43:43

문제 설명

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 A_i개의 라면을 구매하고자 한다(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개의 정수 A₁, ···, A_N가 사이에 공백을 두고 주어진다.

출력

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

문제 풀이

이전 Skyline문제를 이 문제를 풀기 위해 공부했다. 사실상 똑같은 문젠데왜 난이도 차이가 한 티어나 차이나는지 모르겠다. 그리디 문제로 Skyline과 똑같이 풀었다. 자세한 내용은 Skyline 문제 풀이 참고

코드

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));

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N+2];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int minCnt = 0;
		for(int i=0; i<N; i++) {
			if(arr[i+1] > arr[i+2]) {
				// 2개짜리
				int cycle = Math.min(arr[i], arr[i+1] - arr[i+2]);
				for(int j=0; j<2; j++) {
					arr[i+j] -= cycle;
				}
				minCnt += 5*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 += 7*cycle;
				
				cycle = arr[i];
				arr[i] -= cycle;
				minCnt += 3*cycle;
			}
			else {
				int 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 += 7*cycle;
				
				cycle = Math.min(arr[i], arr[i+1]);
				for(int j=0; j<2; j++) {
					arr[i+j] -= cycle;
				}
				minCnt += 5*cycle;
				
				cycle = arr[i];
				arr[i] -= cycle;
				minCnt += 3*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;
    cin >> N;
    vector<int> arr(N + 2);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int minCnt = 0;
    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 += cycle * 5;

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

            // 1묶음
            cycle = arr[i];
            arr[i] -= cycle;
            minCnt += cycle * 3;
        } 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 += cycle * 7;

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

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

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

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

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