오랜만에 DP 문제를 풀어보았다. 정수 삼각형을 입력받아 저장한 뒤, 최종적으로 가장 큰 수를 만들어 가는 문제이다. 단, 선택할 수는 다음행의 수 중, 왼쪽, 오른쪽 둘 중 하나만 선택 가능하다. 즉, 7에서 선택할 수 있는 수는 3, 8 둘 중 하나이다. 이런 방식으로 하나씩 더해 나가 가장 큰 수를 만들면 된다. 얼핏 보면, 선택할 수 있는 수 중에 큰 수를 선택해서 진행하면 되는 탐욕 법 문제로 볼 수 있다. 하지만, 그 다음 상황은 모르기 때문에 탐욕 법은 항상 올바른 답을 주지 않는다. 따라서, 동적 계획법을 이용하여 답을 구해내면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Triangle { public static voi..
