[백준 / BOJ] 1932 정수 삼각형

문제

출처 : www.acmicpc.net/problem/1932

1932번: 정수 삼각형

정수 삼각형을 입력받았을때,

합이 최대가 되는경로를 찾는문제이다 (각 층에선 한 정수만 더 할수있음)

예를들어

 

을 입력받으면, 최대경로는 1 -> 3 -> 6 = 10이 된다.

 

 

풀이

N을 입력을 받고 정수삼각형의 각 정수 입력마다 최댓값을 찾아줬다.

위 정수삼각형에서 규칙을 찾을수있는데, 1층에는 정수가 1개, 2층에는 정수가 2개 ,3층에는 3개...순으로 늘어나는것이다.

이를 응용하면 부모노드에 연결되어있는 자식노드의 인덱스를 알수있다.

예를들어,

 

1. 정수 3은 2층에 위치해있다.

2. 정수 3의 인덱스는 3이다.

3. 정수 3의 자식노드 인덱스는 (정수 3의 인덱스 + 정수 3의 층) -> (3 + 2) = 5이다.

4. 문제에 삼각형이라는 조건이 있음으로 부모는 항상 2개의 자식을 갖고있다. (정수 3의 인덱스 + 정수 3의 층 + 1) -> (3 + 2 + 1) = 6 또한 자식인덱스이다.

 

위 과정을 좀만 변형하면 자식노드에 해당하는 부모노드도 알수있다.

그러면 아래와 같은식이 나오는데,

max( (자식노드의 인덱스 - 자식노드의 층) , (자식노드의 인덱스 - 자식노드의 층 - 1) ) + 입력값;

이 식을 이용해 왼쪽부모에서 오는값과 오른쪽 부모에서 오는값중 큰값을 선택해 해당 노드에 저장한다.

이것을 매 입력마다 해주면 답이나온다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1932%20%EC%A0%95%EC%88%98%EC%82%BC%EA%B0%81%ED%98%95/main.cpp

devxb/JJUNalgo