[Algorithm] ๐ ์ธํ๋ฆฌ ์๋ผ๋ด๊ธฐ
0. ๋ฌธ์
๋๋น๊ฐ ๊ฐ๊ณ ๋์ด๊ฐ ๋ค๋ฅธ ํ์๋ค์ด ๋ถ์ด์ ์ธํ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๊ณ ์์ ๋, ์ธํ๋ฆฌ์์ ์๋ผ ๊ฐ์ฅ ํฐ ์ง์ฌ๊ฐํ์ ๋ง๋ค์ด๋ผ
์ ๋ ฅ
ํ ์คํธ ์ผ์ด์ค(C)
๋๋ฌด ํ์์ ์ซ์
๋๋ฌด ํ์์ ๊ฐ ๋์ด
์ถ๋ ฅ
๊ฐ์ฅ ํฐ ์ง์ฌ๊ฐํ์ ๋์ด
1. ๋ฌธ์ ๊ฐ๋จ ํด์
๋ถ์ด์๋ ํ์์์ ์๋ฅผ ์ ์๋ ๊ฐ์ฅ ํฐ ์ง์ฌ๊ฐํ์ ๋์ด๋ฅผ ๊ตฌํด๋ผ
2. ์์ด๋์ด
๐ก ์ด 3๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ๊ฐ๋ฅํจ
1) ๋ฐ์ ์ ์๋์ ๋ ์ผ์ชฝ ๋ถ๋ถ์์์ ์ง์ฌ๊ฐํ์ด ๊ฐ์ฅ ํด ๋
2) ๋ฐ์ ์ ์๋์ ๋ ์ค๋ฅธ์ชฝ ๋ถ๋ถ์์์ ์ง์ฌ๊ฐํ์ด ๊ฐ์ฅ ํด ๋
3) ์ค๊ฐ๋ถํฐ ์์ํด์ ๋์ด๊ฐ ๋์ ์ชฝ์ผ๋ก ๋ํ๋๊ฐ์ ๋์ ์ง์ฌ๊ฐํ์ด ๊ฐ์ฅ ํด ๋
1,2 ๋ ๋ถํ ์ ๋ณต์ ํตํด์
3์ ์ค๋ฅธ์ชฝ ์ผ์ชฝ์ ๋น๊ตํด์ ๋์ด๊ฐ ๋์์ชฝ์ผ๋ก ๊ณ์ํด์ ์ง์ฌ๊ฐํ์ ๋์ด๋ฅผ ๋ํ๊ฐ๋ ์ฝ๋๋ฅผ ํตํด์ ํด๊ฒฐํ ์ ์์
3. ํต์ฌ ํ์ด
1) ๋ถํ ์ ๋ณต
int ret = Math.max(solve(left,mid), solve(mid+1,right));
2) 3์ ๊ฒฝ์ฐ
while(left < low || high < right) {
if(high < right && (low == left || arr[low-1] < arr[high+1])) {
++high;
height = Math.min(height, arr[high]);
} else {
--low;
height = Math.min(height, arr[low]);
}
ret = Math.max(ret, height*(high-low+1));
}
4. ์ฝ๋
import java.util.Scanner;
public class Fence {
static int n;
static int arr[];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int C = sc.nextInt();
for(int i=0; i<C; i++) {
n = sc.nextInt();
arr = new int[n];
for(int j=0; j<n; j++) {
arr[j] = sc.nextInt();
}
System.out.println(solve(0,n-1));
}
}
static int solve(int left, int right) {
if(left == right) return arr[left];
int mid = (left+right)/2;
int ret = Math.max(solve(left,mid), solve(mid+1,right));
int low = mid, high = mid+1;
int height = Math.min(arr[low], arr[high]);
ret = Math.max(ret, height*2);
while(left < low || high < right) {
if(high < right && (low == left || arr[low-1] < arr[high+1])) {
++high;
height = Math.min(height, arr[high]);
} else {
--low;
height = Math.min(height, arr[low]);
}
ret = Math.max(ret, height*(high-low+1));
}
return ret;
}
}
5. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ ์ธํ๋ฆฌ ์๋ผ๋ด๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-์ธํ๋ฆฌ-์๋ผ๋ด๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ
์ธ ๋ฐ๊ฒฌ์ ์ ๋
(Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค