문제 원본 :
1932번: 정수 삼각형
문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는
www.acmicpc.net
출처 : 1994 IOI(국제정보올림피아드) 1번
풀이법은 다음과 같습니다.
먼저 적당한 배열을 설정하여 삼각형을 입력 받습니다. (본문에서는 int형 배열 t)
정답과 연산과정이 저장될 배열로써 또 다른 배열을 선언합니다. (본문에서는 int형 배열 s)
입력받은 삼각형을 하나하나 탐색하면서 그때마다 가져갈 수 있는 최댓값을 챙겨갑니다.
자신의 위치로 들어올 수 있는 두 개의 칸들 중 최댓값를 가져옴으로써 구현할 수 있습니다.
배열 s의 가장 마지막 줄에 남은 값들 중 최댓값을 찾아 출력하면 문제를 만족하는 정답을 얻을 수 있습니다.
'OJ 문제풀이 > BOJ' 카테고리의 다른 글
| BOJ #11053 가장 긴 증가하는 부분 수열 (0) | 2019.10.07 |
|---|---|
| BOJ #1976 여행 가자 (0) | 2019.09.24 |
| BOJ #10026 적록색약 (0) | 2019.09.23 |
| BOJ #6198 옥상 정원 꾸미기 (0) | 2019.09.22 |
댓글