furyhunter   3년 전

dp라는 배열에 각 줄의 양쪽 max값과 그때의 삼각형에서의 index를 저장해서

다음 단계의 값을 구할 때 이용하도록 재귀 없이 코드를 짜봤습니다.

이렇게 된 경우 예제는 잘 풀리길래 제출해봤는데 오답이 나오더라구요

좀더 생각해보니까

5

3

3 3

3 0 3

3 0 0 3

3 0 50 0 3

같은 식으로 입력이 들어올 경우 제대로 결과가 안나오더라구요 ㅎㅎ

혹시 이런 경우까지 다 잡을 수 있도록 동적계획법을 적용하려면 어떻게 해야할지 조언해주시면 감사하겠습니다!

onjo0127   3년 전

삼각형의 맨 위 꼭짓점을 (1,1)이라고 했을 때

dp[i][j] = (1,1)에서 (i,j)까지 내려오는 데 얻을 수 있는 수의 합의 최대값

이라고 정의하고 풀어보세요 ㅎㅎ

ldg1291   3년 전

배열
int dp[2][555]
를 이용합니다.
여기서 dp[0][]은 이전 층까지의 합이 저장된 곳, dp[1][]은 이번 층의 합을 저장할 곳입니다.
그렇다면 x 층의 i번째 에서의 합은
dp[1][i ] = max(dp[0][i-1], dp[0][i]) + tri[x][i] 가 된다는 것을 알 수 있죠 (물론 i가 시작이나, 끝일 땐 따로 처리를 해줘야합니다)
dp[1][]을 모두 구하고 나면 dp[0][]으로 dp[1][]의 값들을 복사해준 뒤, 다음 x+1번 째 층을 계산하면 될 것 같습니다.
문제의 예제 input을 생각해보면
---------------------------------------------
x = 0 일 때
dp[1][0] = 7

//갱신 끝

dp[0][0] = dp[1][0]
---------------------------------------------
x = 1 일 때 
dp[1][0] = 7+3
dp[1][1] = 7+8

//갱신 끝

dp[0][i] = dp[1][i]
-------------------------------------------
...... 
-------------------------------------------
x = k 일 때
dp[1][0] = dp[0][0] + tri[k][0]
dp[1][k] = dp[0][k-1] + tri[k][k]
else
dp[1][i] = max(dp[0][i-1], dp[0][i]) + tri[k][i]

//갱신 끝

dp[0][i] = dp[1][i]
----------------------------------------------
...
이런식으로 가겠죠

furyhunter   3년 전

조언 덕분에 잘 해결했습니다!

어떤 정보를 저장해야할지 처음 생각해내는게 참 어렵네요

감사합니다!

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