목록1932 (1)

두치의 개발공부

BaekJoon_1932(정수 삼각형)

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 배열을 피라미드 형식으로 그려서 확인 하면 훨씬 보기 편하다. 위에서 아래로 내려오면서 숫자를 더하는 방향보다는, 아래에서 위의 어떤 숫자와 더할 것인지 선택하는 방향으로 생각하면 좀 더 쉽게 접근 할 수 있다. 7 -1 3 8 -2 8 1 0 -3 3번째의 8은 2번째의 3과 더할 수 밖에 없다. 3번째의 0은 2번째의 8과 더할 수 밖에 없다. 3번째의 1은 2번째의 3과 8 중에서 큰 값을 더하면 된다. 이를 점화식으로 나타내면 아래와 같다. j ..
알고리즘 2022. 5. 3. 22:21
이전 Prev 1 Next 다음