[Algorithm] ๐Ÿ“์‚ผ๊ฐํ˜• ์œ„์˜ ์ตœ๋Œ€ ๊ฒฝ๋กœ

HaJingJingยท2021๋…„ 4์›” 22์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
11/119

0. ๋ฌธ์ œ

6
1 2
3 7 4
9 4 1 7
2 7 5 9 4
์œ„ ํ˜•ํƒœ์™€ ๊ฐ™์ด ์‚ผ๊ฐํ˜• ๋ชจ์–‘์œผ๋กœ ๋ฐฐ์น˜๋œ ์ž์—ฐ์ˆ˜๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งจ ์œ„์˜ ์ˆซ์ž์—์„œ ์‹œ์ž‘ํ•ด, ํ•œ ๋ฒˆ์— ํ•œ ์นธ์”ฉ ์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐ€ ๋งจ ์•„๋ž˜ ์ค„๋กœ ๋‚ด๋ ค๊ฐ€๋Š” ๊ฒฝ๋กœ๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ฒฝ๋กœ๋Š” ์•„๋ž˜ ์ค„๋กœ ๋‚ด๋ ค๊ฐˆ ๋•Œ๋งˆ๋‹ค ๋ฐ”๋กœ ์•„๋ž˜ ์ˆซ์ž, ํ˜น์€ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ์ˆซ์ž๋กœ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋•Œ ๋ชจ๋“  ๊ฒฝ๋กœ ์ค‘ ํฌํ•จ๋œ ์ˆซ์ž์˜ ์ตœ๋Œ€ ํ•ฉ์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

์ž…๋ ฅ
์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜ C(C <= 50)๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ์ค„์—๋Š” ์‚ผ๊ฐํ˜•์˜ ํฌ๊ธฐ n(2 <= n <= 100)์ด ์ฃผ์–ด์ง€๊ณ , ๊ทธ ํ›„ n์ค„์—๋Š” ๊ฐ 1๊ฐœ~n๊ฐœ์˜ ์ˆซ์ž๋กœ ์‚ผ๊ฐํ˜• ๊ฐ ๊ฐ€๋กœ์ค„์— ์žˆ๋Š” ์ˆซ์ž๊ฐ€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ์ˆซ์ž๋Š” 1 ์ด์ƒ 100000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ถœ๋ ฅ
๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ํ•œ ์ค„์— ์ตœ๋Œ€ ๊ฒฝ๋กœ์˜ ์ˆซ์ž ํ•ฉ์„ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

1. ๋ฌธ์ œ ๊ฐ„๋‹จ ํ•ด์„

๊ฐ ์นธ์— ์ ํ˜€ ์žˆ๋Š” ์ˆซ์ž๋งŒํผ ์˜ค๋ฅธ์ชฝ ๋˜๋Š” ์•„๋ž˜์ชฝ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Œ ๋ชฉ์ ์ง€์— ๋„์ฐฉํ•˜๋Š” ๊ฒฝ๋กœ์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฒƒ์„ ์ฐพ๊ณ  ์ถœ๋ ฅ

2. ์•„์ด๋””์–ด

๋ฉ”๋ชจ์ด์ œ์ด์…˜ : ์ €์žฅํ•ด๋†“๊ณ  ์‚ฌ์šฉํ•˜๊ธฐ (์ค‘๋ณต ์—ฐ์‚ฐ ๊ฐ์†Œ)

3. ํ•ต์‹ฌ ํ’€์ด

1) ๋ฉ”๋ชจ์ด์ œ์ด์…˜

int ret = cache[y][x];
if(ret != -1) return ret;
return ret = Math.max(path(y+1,x), path(y+1, x+1)) + triangle[y][x];

4. ์ฝ”๋“œ

import java.util.Scanner;

public class DP_EX_3 {
	static int n, triangle[][] = new int[100][100];
	static int cache[][] = new int[100][100];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int tc = sc.nextInt();
		
		while(tc > 0) {
			n = sc.nextInt();
			
			int size = 0;
			for(int i=0; i<n; i++) {
				size++;
				for(int j=0; j<size; j++) {
					triangle[i][j] = sc.nextInt();
					cache[i][j] = -1;
				}
			}
			
			System.out.println(path(0,0));
			tc--;
		}
	}
	
	static int path(int y, int x) {
		if(y == n-1) return triangle[y][x];
		
		int ret = cache[y][x];
		if(ret != -1) return ret;
		return ret = Math.max(path(y+1,x), path(y+1, x+1)) + triangle[y][x];
	}

}

5. ๊ฒฐ๊ณผ

์ฑ…๋Œ€๋กœ ํ’€์—ˆ๋Š”๋ฐ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋‚˜๋Š” ๊ฑฐ๋Š” .. ์™œ ๊ทธ๋ ‡์ง€?

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€