[BOJ] 14719. 빗물

31 Oct 2020

Reading time ~1 minute

접근방식 1 : 완전탐색(Brute Force)
- 완전탐색(BruteForce) 풀이 구현
접근방식 2 : DP(Dynamic Programming)
- DP(Dynamic Programming) 풀이 구현

해당 문제는 백준 온라인 저지(BOJ)의 14719번 빗물에서 풀어보실 수 있습니다.

접근방식 1 : 완전탐색(Brute Force)

for문이 2번 중첩되어 $O(N^2)$ 의 시간복잡도를 가지게 됩니다.

빗물 완전탐색 접근방식

완전탐색(BruteForce) 풀이 구현

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int H=sc.nextInt();
		int W=sc.nextInt();
		
		int height[]=new int[W];				
		for (int i = 0; i < height.length; i++)
			height[i]=sc.nextInt();
				
		int answer=0;
		int left_max,right_max;
		for (int cursor = 0; cursor < height.length; cursor++) {
			left_max = height[cursor];
			right_max = height[cursor];
			for (int left_cursor = cursor; left_cursor >=0 ; left_cursor--)
				left_max=Math.max(height[left_cursor],left_max);
			
			for (int right_cursor = cursor; right_cursor < height.length; right_cursor++) 
				right_max=Math.max(height[right_cursor],right_max);
			
			answer+=Math.min(left_max,right_max)-height[cursor];
		}
		System.out.println(answer);
	}
}

접근방식 2 : DP(Dynamic Programming)

for문을 1번만 사용하도록 변경함으로써 $O(N)$ 의 시간복잡도를 가지게 됩니다. 1번 for문이 2번 중첩되는 완전탐색(Brute Force)을 사용한 방식보다 시간복잡도를 개선할 수 있습니다.

빗물 DP 접근방식

DP(Dynamic Programming) 풀이 구현

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();

		int[] height = new int[W];
		int[] left_max = new int[W];
		int[] right_max = new int[W];

		int answer = 0;
		
		for (int i = 0; i < W; i++) {
			height[i] = sc.nextInt();					
		}
		
		left_max[0] = height[0];
		for(int left_cursor = 1 ; left_cursor < W ; left_cursor++)
			left_max[left_cursor] = Math.max(height[left_cursor], left_max[left_cursor-1]);
		
		right_max[W - 1] = height[W - 1];
		for(int right_cursor = W - 2 ;  right_cursor >0  ; right_cursor--)
			right_max[right_cursor] = Math.max(height[right_cursor], right_max[right_cursor+1]);
				
		for(int cursor = 1 ; cursor < W - 1 ; cursor++)
			answer+= Math.min(left_max[cursor], right_max[cursor]) - height[cursor];
		
		System.out.println(answer);		
	}
}