[C++] 백준 1932번 정수 삼각형

다이나믹 프로그래밍 문제.

경우의 수를 나눠서 Bottom Up 방식으로 문제를 해결하면 된다.

처음에 그림을 보고 트리 -> 그래프 탐색인 줄 알았는데 문제를 읽어보고 그림을 그려보니까

다이나믹 프로그래밍이란 것을 알았다.

 

그림을 보면 각 노드에서 아래로 내려오면서 그 노드의 최대값을 갱신해 나가면 된다.

이 때 방향을 보면 맨 첫번째 노드는 각 전단계의 첫번째 노드에서만 온다는 것을 알 수 있다.

그리고 마지막 노드는 전단계의 마지막 번째의 노드에서만 온다는 것을 알 수 있다.

첫번째, 마지막 둘 다 아니라면 전 단계의 왼쪽, 오른쪽 노드에서 온다는 것을 알 수 있다.

 

점화식을 세우면 다음 그림과 같다.
dp[i][j]는 i, j의 최대값을 저장하는 배열이고 triangle[i][j]는 i, j의 가지고 있는 값을 저장하는 배열이다.

각 단계별로 점화식을 세우면 위와 같다.

1. 첫번째 층에 있는 것은 어차피 값과 같으므로 초기화 해준다.
2. 두번째 층부터는 첫번째인지, 마지막인지, 둘 다 아닌지로 고려해서 코드를 짜면 된다.

• j == 1, 첫번째인 경우 전 단계의 첫번째에서 온 것이다.
• j == i, 해당 층의 마지막인 경우 전 단계의 마지막에서 온 것이다. 전 단계의 마지막은 현재 단계의 마지막에서 -1을 해준 것과 같다. (전 단계보다 원소가 한 개씩 늘어나므로)
• 둘 다 아닌 경우에는 왼쪽에서 온 것과 오른쪽에서 온 것 중 큰 값을 받아오면 된다. 왼쪽에서 온 것은 현재 인덱스에서 -1을 해준 것이고 오른쪽에서 온 것은 현재 인덱스와 같은 값이다.

 

코드

 

사용한 STL과 변수

max 메서드를 사용하기 위해서 algorithm STL을 사용했다.

몇 층인지를 받는 n과 해당 노드에서 얼마의 값을 갖는지를 저장하는 triangle 배열,

각 층 각 단계에서 최대값을 저장하는 dp 배열,

결과값을 출력하는 result 변수를 만들었다.

 

메인함수 - 1

처음에 n과 각 층에서의 값들을 입력받고 저장한다.

그리고 dp[1][1]을 triangle[1][1]로 초기화한다.

그리고 모든 층을 돌면서 Bottom Up 방식으로 dp배열에 값을 저장한다.

값을 저장하는 방식은 위에 세운 점화식을 바탕으로 만든다.

 

메인함수 - 2

그리고 각 층의 마지막 단계에서 반복문을 한번 더 돌려서 결과값을 찾고 출력한다.

 

처음에 j == 1일때와 j == i 일 때 둘 다 dp[i][j] = dp[i-1][j] + triangle[i][j]로 저장해서 틀렸다.

사실 j == i일때에는 마지막 인덱스 이므로 전 단계에서 j - 1로 받아와야 한다.

실버1 DP인데도 큰 문제없이 푼 문제.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.