이 문제를 백트래킹으로 접근하면
시간복잡도가 어떻게 나오나면
1번째 줄에는 경우가 1개, 2번째 줄에는 1 * 2, 3번째 줄에는 1 * 2 * 2, 4번째 줄에는 1 * 2 * 2 * 2... n번째 숫자는 2^(n-1)개가 되는걸 알수있죠.
이 경우를 다 조사하면 시간도 당연히 2^(n-1) 만큼 들겠죠. 아무리 유망하지 않는 부분을 가지 않는다고 한다해도 경우가 크게 많이 줄진 않을것 같습니다.
그래서 이 문제는 각층의 어떠한 위치에 도달할때 수많은 경로를 통해 올수 있지만 '최댓 값'을 구하는 문제이므로 그 곳에 도착했을때 최댓값만 저장하는 방식으로 하면 경우의 수를 대폭 줄일수 있습니다.
예를 들면 예제를 보면
4번째 줄의 2번째 위치의 7에 도달한다고 가정해 봅시다. 그러면 올 수 있는 길은 3번째 줄의 8에서 오거나 1에서 오거나 둘 중 한개 겠죠
그때 처음부터해서 3번째 줄의 8에 도달하는 경로중 최댓값과 처음부터 3번째 줄의 1에 도달하는 경로중 최댓값을 들고 있을 시 4번째 줄의 7에 도달하는 경우를 2가지로 줄일 수 있겠죠.
왜냐면 저희는 최댓값을 찾는 것이니 두군데에 도달하는 최댓값 중 큰 놈이 4번째 7에 도달하는 경로중 가장 큰 경로가 된다는 걸 알 수 있으니깐요.
이러한 방식으로 최댓값을 저장해 나가다 보면 마지막 줄에서 이 삼각형에서 나올수 있는 경로중 최댓값을 저장하고 있겠죠. 그들 중 최댓값을 뽑아내면 답을 구할 수 있겠습니다.
참고로 이렇게 할 경우 시간 복잡도는 숫자 삼각형에 존재하는 숫자들의 갯수인 n(n-1) / 2 개가 되겠죠.
이러한 풀이 방법을 일명 동적 계획법이라고 합니다.
tmmoond8 7년 전
제 풀이는 한정계산법을 썼습니다. 유망성 추론이 엉성하긴 한데..