정수 삼각형1 [C] 1932: 정수 삼각형 이 문제 역시 Dynamic Programming! 역시 규칙찾아 점화식을 구하면 쉽게 풀 수 있다 규칙은 자기 위층의 양 옆까지 수까지의 경로에 있는 수의 합을 저장하는 것하면 되는데 여기서 주의해야 할 것은 각 층의 양끝은 무조건 바로 위쪽 한군데에서만 따로 내려오므로 점화식에서 예외처리를 해줘야한다. 예외처리를 굳이 하고 싶지 않다면 전에 풀었던 Knapsack Problem처럼 배열 양 끝에 0을 추가해주면 한번의 정리가 가능하다. 처음에 이 문제를 풀 때 잘못 이해하여 배열을 500!만큼 잡야아하는줄 알고 재귀함수를 이용해 각 함수를 호출할 때마다 배열의 크기가 최대 500만큼 되도록 잡았는데 사실 이차원배열을 이용하면 최대 250000의 크기를 잡아도 되어 범위였다! 그래서 이차원 배열을 잡고.. 2023. 7. 23. 이전 1 다음