[BOJ] 백준 1932 정수 삼각형 (Swift)

문제

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

1932번: 정수 삼각형

풀이

왼쪽 대각선 혹은 오른쪽 대각선으로 내려오면서 수들을 더해주고, 가장 큰 수를 구하는 문제입니다.

2차원 배열에 입력을 담아줍시다.

이 테두리에 있는 수들은 위에 수에서 내려올 수 있는 경로가 하나밖에 없습니다.

테두리에 있는 수는 x좌표가 0이거나, y좌표와 x좌표가 같은 경우입니다.

x좌표가 0일 때는 (y - 1, x) 에서 내려오는 경로밖에 없습니다.
y좌표와 x좌표가 같은 경우일 때는 (y - 1, x - 1) 에서 내려오는 경로밖에 없습니다.

하지만 테두리에 있지 않은 수는 자신을 기준으로 (y - 1, x - 1), (y - 1, x) 경로에서 내려올 수 있습니다.
가장 큰 수를 만들기 위해서는 (y - 1, x - 1), (y - 1, x) 중 더 큰 값에서 내려와야 합니다.

따라서 다음과 같이 정의할 수 있습니다.

정의 : $f(y,x)$ = (y, x)까지 내려왔을 때, 합이 최대가 되는 경로에 있는 수의 합
초기값 : $f(0,0) = graph(0,0)$
점화식 : $f(y,x)$ =
$if \ \ \ (y == x) \ \ f(y-1,x-1)\ + \ graph(y,x)$
$elif \ \ \ (x == 0) \ \ f(y-1,x)\ + \ graph(y,x)$
$else \ \ \ max(f(y-1,x-1),f(y-1,x))\ + \ graph(y,x)$

그 이후 마지막 층에서 가장 큰 수를 출력해줍시다.

소스코드

후기

합이 최대가 되는 경로를 찾으면서, 점화식을 도출해낼 수 있었습니다.