stompesi   3년 전

고수님들 어떤 케이스가 안되는지좀 알려주세요..

도저희 모르겠네요 ㅠ


tofhddl9   3년 전

일단 n=1일때 totalmax=0를 출력하고 종료하는 케이스도 있을것이구요. 

삼각형에서 내려오면서  윗줄의 max값 3개중 가장 큰 것을 더해주시는데 내려오는 루트는 2개인 것 같네요.

또 for문이 i<n-1 인데 i<n까지 돌아야 마지막 줄까지 계산 할 수 있지 않을까요?

모바일로 본거라 틀릴수도 있지만... 코드 따라가시다가 어려우시면 디버깅 추천드려요

stompesi   3년 전

혹시 , n이 1이면 0이 아니라는 소리이신가요?

현재 단계에서 내려왔을때 까지 선택된 수의 합을 찾는거라 1이면 선택한 수가 없어서 0이아니인가요 ?

문제를 잘 이해를 못하고 있는것같네요. 

stompesi   3년 전

다시 C언어로 바꾸어보았습니다...

내려갈수 있는방법은0,0 에서 오른쪽, 왼쪽 대각선으로 내려가니 

입력을 다음과 같이.. 입력하였을때

5

7

3 8

8 1 0 

2 7 4 4

4 5 2 6 5

------------

최대 경로는 다음과같고..

0 15 

23 0 15 

0 30 0 19 

34 0 32 0 24 


맨 마지막까지 선택한 최대의 값은 30이므로 30을 출력한다. 아닌가요?ㅠㅠ 몇번을 실패하는지모르겟네요 ㅠㅠ


tofhddl9   3년 전

우선, "맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로"는

맨 위층부터 맨 아래층까지 선택한 것들의 최대값을 구하는 것이므로

n=1일때는 그 한 층의 크기가 답이 됩니다.

예를 들어서,

입력이 1

             10 일경우

답으로 10을 출력해야 합니다.


잘못 이해하신 중요한 또 다른 한 가지는

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 라는 입력은


        7
      3  8
    8  1  0
  2  7  4  4 
4  5  2  6  5 의 파스칼 삼각형을 나타낸 것입니다.

따라서 최대 경로의 누적값은 다음과 같겠죠~?

            7
       10   15
   18    16    15
           ....
           ....




stompesi   2년 전

감사합니다.. 너무멍청하게 생각햇네요 ㅎㅎ 덕분에 풀었습니다!!

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