RSS Feed

합이 최소인 부분 삼각 배열

Problem 150

출제 일시 : 2020-08-02 00:01:09

양과 음의 정수로 이루어진 삼각 배열의 내부에서 원소의 합이 최소가 되는 삼각 배열을 찾고자 합니다.

아래 보기에서, 빨간 삼각형으로 표시된 부분 삼각 배열의 합은 -42로 이 조건을 충족합니다.

이제 100 줄짜리 삼각 배열을 만들어 봅시다. 그러기 위해서는 500500 개의 유사 난수가 필요합니다. 선형 합동 생성기(Linear Congruential Generator)를 이용하여 ±219 범위의 유사 난수 sk를 다음과 같이 생성합니다:

t := 0
for k = 1 up to k = 500500:
    t := (615949*t + 797807) modulo 220
    sk := t−219

따라서: s1 = 273519, s2 = −153582, s3 = 450905 이렇게 생성됩니다.

그 다음 생성된 유사 난수를 이용하여 다음과 같이 삼각 배열을 만듭니다:

s1
s2  s3
s4  s5  s6 
s7  s8  s9  s10
...

부분 삼각 배열은 배열의 어디에서나 시작할 수 있고 원하는 만큼 아래로 확장할 수 있습니다. 바로 아래 정수 두 개, 그 아래 정수 세 개, 이런 식입니다.
"부분 삼각 배열 합"을 부분 삼각 배열에 포함된 모든 원소의 합이라고 정의합니다.
이 삼각 배열에서 최소 "부분 삼각 배열 합"을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.