[백준] 1932번 정수 삼각형

역시나 점화식을 짜놓고, 오류 고친다고 오히려 시간을 더 사용한 문제다...

일단 점화식을 짜보자

경로는 무조껀 왼쪽 대각선 혹은 오른쪽 대각선이다.

그렇담 7에서 나가는 3 과 8을 경로로 잡는다고 하면, 7->3(10), 7->8(15) 이다.

가운데의 1에 갈 수 있는 방법은 7->3->1 또는 7->8->1 그러나 7->8->1 이 더 크기 때문에 7->3->1 은 무시한다.

또한 또하나의 법칙이 있는데, 좌측 제일 하단의 4와 우측 제일 하단의 5가 보이는가?

저 길까지 가는 방법은 무조건 첫번째 배열에서 좌측 대각선으로 가거나, 우측 대각선으로 가는 방법밖엔 없다.

예) 7에서부터 시작해서 좌측 하단의 4까지 거리를 만드는 방법은

7->3->8->2->4 순으로 가는 방법밖엔 없다.

우측 또한 마찬가지다.

그럼 여기서 점화식을 세울 수 있는데.

dp = 동적 계획법으로 사용할 배열, arr = 현재 좌표의 값

맨 좌측 또는 맨 우측이 아니라면, 점화식은 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) ( i를 y로 가정, j를 x로 가정 )

맨 좌측(x == 1) 이라면? dp[i][1] = dp[i-1][1] + arr[i][1] ( x가 1이라면 자기 위로밖에 갈 길이 없다)

맨 우측(x == y) 이라면? dp[i][j] = dp[i-1][j-1] + arr[i][j] ( x = y 라면, 그건 현재 좌표가 가장 우측에 있다는 것)

그리고 x 와 y 가 1 이라면 arr[1][1] 의 값을 리턴해주면 된다.

<어떻게 푸는지 풀이예시>

<풀이 소스>

나는 재귀를 돌리는게 약간 익숙하지 않아서, 대부분 dp를 재귀로 풀려고 노력하고 있는데, 이렇게 하지마라 할짓이 못 된다.

memset을 사용한 이유는 모든 입력 배열을 -1로 초기화 시키기 위해서였다. 근데 필요성이 있나 싶다. 하지마라

소스에 보면 R(N,i)가 있는데 이건 x가 몇에서부터 출발하냐에 따라 최댓값을 넣어주기 위해 돌려놨다.

MAX는 dp의 최 하단의 모든 최댓값들중 가장 큰 값을 출력하기위해 만든 변수이다.

맨 처음 이 소스를 짤땐 왜 계속 최댓값을 긁어오지 못하는 거지 라고 했는데.. 그 이유가...

내가 R(N,N) 한번만 돌게 해놨다.. R(N,N)만 돈다는 것은 최 하단 맨 우측에서부터만 시작한다는 거기때문에 

같은 선상에 있는 다른 x 값에 대해선 구해주지 못했었다..

그리고 R(y,x)가 왜 R(x,y)가 아닌 R(y,x)로 됐냐면.. 내가 입력을 받을때 arr[y][x]로 받아놓고 R 함수를 만들때 R(x,y)로 만들어버렸다.. 그래서 변수들까지

다 바꾸긴 귀찮아서 R(y,x)로 바꾸어버렸따...

그럼 이만..