[백준 알고리즘] 1932 정수 삼각형 (21.05.16)

이전 이야기 ....

 

 

2021.05.16 - [알고리즘 스터디] - [백준 알고리즘] 1003 피보나치 함수

[백준 알고리즘] 1003 피보나치 함수

 

 

 

---

 

 

두 번째 동적 프로그래밍 문제는 !!!

 

 

 

백준 1932번 정수 삼각형

 

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

문제 사이트 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

---

 

여기서 핵심 포인트!!!

 

 

- 삼각형 속에서 규칙 찾기

 

- 어떻게 입력받은 값을 관리하는가 !!!!!

 

---

 

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

import java.util.Scanner;

public class Main {

	static int piramid[][];
	
	static int maxSum(int size) {
		int max = piramid[0][0];
		for(int i = 1; i < size; i++) {
			for(int j = 0; j<= i; j++) {
				if(j == 0) piramid[i][j] = piramid[i-1][j] + piramid[i][j];
				else if(j == i) piramid[i][j] = piramid[i-1][j-1] + piramid[i][j];
				else {
					piramid[i][j] = check(piramid[i-1][j-1], piramid[i-1][j]) + piramid[i][j];
				}
				max = check(max, piramid[i][j]);
			}
		}
		return max;
	}
	
	static int check(int a, int b) {
		return (a > b) ? a : b;
	}
	
	
	
	public static void main(String[] args){
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		piramid = new int[n][n];
		for(int i = 0; i< n; i++) {
			for(int j = 0; j<= i ; j++) {
				piramid[i][j] = sc.nextInt();
			}
		}
		int sum = maxSum(n);
		
		System.out.println(sum);
		
	}

}

 

 

코드를 짜게 된 루트를 간단히 설명하자면

 

 

• 먼저 삼각형을 배열로 어떻게 넣을 지 고민해봤다!!

삼각형 배열로 확인하기

 

• 보이는 것처럼 부모는 자신의 바로 위 혹은 왼쪽 위가 된다!!

 

=>  식으로 표현하자면 piramid[i-1][j-1] OR piramid[i-1][j] 가 된다는 것!!!

 

 

• 하지만, 항상 그런 것은 아니다!!!!!

 

• 0열인 경우에는 부모가 바로 위 단 하나뿐!!!!

 

• 행과 열이 같은 경우에는 부모가 왼쪽 위 단 하나뿐이다!!!!

 

 

 

이 모든 것을 식으로 정리하고 코드로 작성하면

 

위 같은 코드가 나오게 되는 것이다!!!!!!

 

 

 

또한, 여기서 사용한 자신에게 위로부터 계속 더해가는 원리는

 

몇 주 전,  BFS/DFS 할 때 배웠던 스킬이다!!!

 

2021.05.02 - [알고리즘 스터디] - [백준 알고리즘] 2178 미로 탐색 (21.05.02)

[백준 알고리즘] 2178 미로 탐색 (21.05.02)

 

 

 

 

 

 

 

---

 

 

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

 

 

백준 1932번 채점 결과

 

 

 

 

 

 

 

---

스터디하면서 얻은 것들

• 매번 max 값을 확인하지 않고 마지막 줄에서 찾는 방법도 있다!!

 

 

 

 

 

 

---

 

 

 

오늘은 

 

모두 이 문제를 풀면서 지쳐버린 관계로

 

 

 

 

이게 끝!!!!!!!!!!!!!!!!!!!!!!