정수 삼각형

정수 삼각형 링크 :www.acmicpc.net/problem/1932

1932번: 정수 삼각형

해당 문제는 문제를 읽으시면 아시겠지만 정수로 이루어진 삼각형에서

제일 상단 노드인 0번째 노드부터 시작하여 내려오면서 리프노드 까지 더했을때 가장큰 수를 찾는것 이었습니다.

따라서 처음에는 dfs로 풀어야하나 생각해서 그렇게 풀었더니 시간초과가 나더라구요;;;

따라서 메모이제이션을 사용하여 풀었습니다.

 

루트 노드, 특정 트리의 높이에서 첫번째와 마지막 노드 이렇게 세개의 노드를 제외하고는 모두 두개의 부모 노드를 갖는데요(왼쪽, 오른쪽 이렇게 두개가 됩니다.)

 

삼항 연산자로 해당 부모노드들중 큰 수를 가져와서 더해주었습니다

특정 트리의 높이에서 첫번째와 마지막 노드는 하나의 부모를 갖습니다.

첫번째노드는 오른쪽의 부모를 갖고 마지막 노드는 왼쪽의 부모노드를 택하게 됩니다.

이를 코드로 짜게되면

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 정수삼각형 {
	static int TreeHeight;
	static int arrSize;
	static int[] arr;
	static int answer = 0;
	static int idx = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TreeHeight = Integer.parseInt(br.readLine());

		for (int i = 1; i <= TreeHeight; i++) {
			arrSize += i;
		}

		arr = new int[arrSize];

		for (int i = 1; i <= TreeHeight; i++) {
			st = new StringTokenizer(br.readLine());

			if (i == 1) {
				arr[idx++] = Integer.parseInt(st.nextToken());
				continue;
			}

			for (int j = 1; j <= i; j++) {
				if (j == 1) {
					// 오른쪽만
					int num = Integer.parseInt(st.nextToken());
					int val = arr[idx - i + 1] + num;
					arr[idx++] = val;
				} else if (j == i) {
					// 왼쪽만
					int num = Integer.parseInt(st.nextToken());
					int val = arr[idx - i] + num;
					arr[idx++] = val;
				} else {
					int num = arr[idx - i + 1] > arr[idx - i] ? arr[idx - i + 1] : arr[idx - i];
					int val = num + Integer.parseInt(st.nextToken());
					arr[idx++] = val;
				}
			}
		}

		for (int i = 1; i <= TreeHeight; i++) {
			answer = Math.max(answer, arr[idx - i]);
		}

		System.out.println(answer);
	}
}

이렇게 됩니다.

중요한것은 자신의 부모노드로 가는건데요.

'arr[idx - i + 1] ' 자신의 index에서 자신이 위치한 높이를 빼고 +1을 해주면 오른쪽 부모노드를 택하게됩니다

'arr[idx -i]' 그렇다면 +1을 안하면 왼쪽 부모노드를 택하게 되겠죠?ㅋ

 

근데 여기서 또다른 팁을 드리자면 완전 이진 트리의 경우(정수 삼각형은 완전이진트리가 아니기때문에 idx-i+1과같은 접근법을 사용했습니다.)

 

왼쪽 자식노드 = 부모노드 index*2

오른쪽 자식노드  = 부모노드 index*2+1 로 접근할 수 있습니다.