BOJ_11835_Skyline (Java, C++)

[Platinum V] Skyline - 11835

문제 링크

성능 요약

메모리: 14140 KB, 시간: 104 ms

분류

다이나믹 프로그래밍, 그리디 알고리즘

제출 일자

2024년 12월 7일 16:06:07

문제 설명

You want to have in your city a beatiful skyline. You have decided to build N skyscrapers in a straight row. The i-th of them should have exactly h[i] floors.

You have got offers from different construction companies. One of them offers to build one floor in any of the skyscrapers for 3 Million Euros. The other one offers to build one floor in each of two neighbouring skyscrapers for 5 Millions in total. Note that it doesn’t matter whether these floors are on the same height or not. The third one can build one floor in each of three consecutive skyscrapers for only 7 Millions.

You can build the floors in any order you want. Calculate the minimal possible total amount of money needed to finish the construction.

입력

The first line contains integer number N (1 ≤ N ≤ 300). The second line contains space separated N integer numbers, h[1], h[2], ..., h[N], 1 ≤ h[i] ≤ 200.

출력

Output one integer number: the amount of money, in Millions.

문제 풀이

각 위치에서 어떤 연산을 먼저 수행하는 것이 최적인지를 판단해야 한다. 각 위치 i에서 현재 수 arr[i]를 0으로 만들어야 한다. a[i+1]과 a[i+2]를 비교하여 두 가지 경우로 나눌 수 있다.

• Case 1: a[i+1] > a[i+2]인 경우

1. 먼저 2개묶음 연산으로 min(a[i], a[i+1] - a[i+2])만큼 두 번째 수와 세 번째 수의 차이를 줄인다.

2. 그 다음 3개묶음 연산을 min(a[i], min(a[i+1], a[i+2]))만큼 한다.

3. 마지막으로 남은 수에 대해 1개 묶음 연산을 수행합니다.

• Case 2: a[i+1] ≤ a[i+2]인 경우

1. 먼저 3개묶음 연산을 min(a[i], min(a[i+1], a[i+2]))만큼 최대한 수행한다.

2. 그 다음 2개묶음 연산 count = min(a[i], a[i+1])만큼 수행한다.

3. 마지막으로 남은 수에 대해 1묶음 연산을 수행한다.

• 시간 복잡도

  • 각 위치에서 최대 3번의 연산을 수행하고 전체 시간 복잡도는 O(N)

코드

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++ 코드