tmmoond8   3년 전

제 풀이는 한정계산법을 썼습니다. 유망성 추론이 엉성하긴 한데..

king7282   3년 전

이 문제를 백트래킹으로 접근하면

시간복잡도가 어떻게 나오나면

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   3년 전

감사합니다. 문제 접근법을 다르게 해서 풀어볼께요 감사해요!

tmmoond8   3년 전

king7282님 덕분에 문제 풀었습니다. 감사합니다.!

댓글을 작성하려면 로그인해야 합니다.