백준 1932

2020. 3. 2. 18:23

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는

www.acmicpc.net

- 삼각형의 위에서 부터 길을 만들어 각 수 를 더하였을 때 가장 큰 값이 되도록 하는 길을 쫓아가서

- 그 값을 출력하는 문제입니다.

- vector 두개를 이용하여 들어오는 값과 vector 0과 들어오는 값을 비교하여 vector 1에 저장하고

- 그다음 들어오는 값들은 vector 1과 들어오는 값들을 비교하고 더해 vector 0에 저장하는 작업을 반복한 후

- 물론 작업이 끝난 배열은 초기화를 해야 합니다 (그 다음 줄에서 넣어야하므로)

- 마지막에 n의 값에 따라서 vector 0 또는 vector 1 을 내림차순 으로 정렬 한후 index 0의 값을 출력하였습니다.

- 값을 더하고 저장하고 더하고 저장하고 를 반복하는 작업이라고 생각 하시면 될거 같습니다.

- 그리고 각 입력의 처음과 마지막은 비교를 할 필요없이 바로 0번쨰 index그리고 마지막 index랑 더해서 넣으면 됩니다.

<필기>