![[백준,BOJ 1932] 정수 삼각형(JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FIEgtD%2Fbtqz27DPQLX%2FTW4R2fgstEacwpUXtFm11K%2Fimg.png)
-내 생각
이번 문제 이전에 풀었던 RGB거리 문제 덕에 이러한 비용 문제, 또는 숫자의 누적 문제는 문제에서 주어진 입력과 동일하게 배열을 하나 만들어 해당하는 지점까지의 결과를 저장해 나가면서 풀면 된다는 것을 알 수 있었다.
이 문제에서 약간 혼동될 수 있는 부분이 있다고 생각하는데, 문제 부분의 글과 그림을 보면 정삼각형의 형태로 입력이 주어지는 것처럼 보이지만, 예제 입력 1을 보면 알 수 있듯이 열이 +1씩 되면서 입력이 되는 것을 알 수 있다. 그렇기 때문에 문제에서 말하는 왼쪽 대각선과 오른쪽 대각선의 의미는 사실상 배열의 개념에서 생각해 볼 때, 자신이 속한 열과 그다음 열을 의미한다는 것이다. 예를 들어, 삼각형의 2층에서 8이 선택할 수 있는 숫자는 자신이 속한 행인 1과, 그다음 열인 0인 것이다.
-해법
위에 언급했듯이 입력과 동일한 배열은 만들면 된다는 것을 알게 되었다. 그렇다면 그 배열에 누적된 값들은 어떠한 방식으로 저장해주어야 할까? 실제로 해당 삼각형의 누적된 모습을 노트에 그려보면 1번 열에 속한 값들은 모두 이전의 행값 + 자신의 값이라는 것을 알 수 있다. 예를 들어 2층부터 3의 자리에 누적될 값은 같은 열이면서 이전행의 값인 7+ 자신의 값 3으로 10이 되는 것이다. 이러한 현상이 발생하는 이유는 위에서 서술했듯, 자신이 속한 행과 그 다음행만을 선택할 수 있기 때문인데, 1번 열의 경우에는 자신이 속한 행을 제외하고는 이전의 행으로부터 영향을 받을 수가 없기 때문이다.
하지만 1번 열을 제외하고는 상황이 달라진다. 왜냐하면 이전 행의 영향을 받기 때문인데, 예를 들어 3층의 1번 값에 누적될 결과는 (2층의 3번에 누적된 값 + 자신의 값) 또는 (2층의 8번에 누적된 값 + 자신의 값) 중 큰 값을 골라야 한다.
위의 내용을 요약해 점화식을 세워보면 (I는 행, J는 열, DP는 누적값 저장 배열, COST는 각 칸에 저장된 값 배열)
if(j==1) // 1번 열의 경우
dp[i][j] = cost [i][j]+ dp [i-1][j]; // 자신의 값 + 자신이 속한 열의 이전 행까지 누적된 값
else // 2 ~ N번 열의 경우
dp[i][j] = cost [i][j] + Math.max(dp [i-1][j], // 자신의 값 + 이전 행의 자신이 속한 열의 값과 자신이 속한 열의 이전 값 중 큰 값
과 같이 세울 수 있다. 이것을 사용해 코딩을 해보면 아래와 같다.
import java.util.*;
public class Main {
static int n; // N층 변수
static int dp[][], cost[][]; // 누적값 저장 배열, 각 층의 값 저장 배열
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
// 1번 인덱스부터 사용하기 때문에 +1
dp = new int[n+1][n+1];
cost = new int[n+1][n+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=i;j++) { // i의 값에 따라 열의 수를 조정해준다.
cost[i][j] = sc.nextInt();
}
}
dp[1][1] = cost[1][1]; // 최상층 값은 미리 누적값에 저장해둔다.
for(int i=2;i<=n;i++) { // 최상층의 아래층 부터 n까지 반복
for(int j=1;j<=i;j++) { // 1번열부터 i까지 반복, i가 2일 경우 2까지 3일 경우 3까지...
// 점화식
if(j==1)
dp[i][j] = cost[i][j]+ dp[i-1][j];
else
dp[i][j] = cost[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
}
}
int max = Integer.MIN_VALUE;
for(int i=1;i<=n;i++) { // n층에 저장 된 값들 중 최댓값을 찾으면 된다.
if(dp[n][i]>max) {
max = dp[n][i];
}
}
System.out.println(max);
}
}
이전 풀이를 보면 무조건적으로 dp배열을 이용한 메모 이제이 션 기법을 활용하려는 모습이 보이는데, 일반적으로 Top-down 방식의 재귀 함수를 이용하는 경우에 dp배열을 이용하여 풀어야 하지만, 반복문을 사용하는 Bottom-up 방식은 작은 문제부터 결과를 도출해내는 방식이므로 굳이 dp 배열을 사용할 필요가 없다. 왜냐하면 데이터로 주어지는 값이 있기 때문에 그 값들을 경신시켜 주고, 사용하면 그것 또한 메모이제이션의 한 종류라 할 수 있기 때문이다.
그렇기에 문제를 푸는 기본 개념은 이전의 풀이와 큰 차이가 없지만, 코드상으로는 쓸데없는 dp배열을 사용하지 않고 표현할 수 있다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 데이터 입력
int n = in.nextInt();
int a[][] = new int [n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++) {
a[i][j] = in.nextInt();
}
}
// 1번 행부터
for(int i=1;i<n;i++) {
for(int j=0;j<=i;j++) {
// j-1열이 >=0을 만족하면, 이전 행의 자신과 같은열(오른쪽 대각선), 자신-1 열(왼쪽 대각선) 중 큰 값을 더해준다.
if(j-1>=0)
a[i][j]+=Math.max(a[i-1][j], a[i-1][j-1]);
// 만족하지 않는 좌,우 값들은 자신과 같은열(왼쪽 또는 오른쪽 대각선)의 값만 더해줄 수 밖에 없다.
else
a[i][j]+=a[i-1][j];
}
}
int max = Integer.MIN_VALUE;
// 마지막행에서 취할 수 있는 최댓값을 가져오면 된다.
for(int i=0;i<n;i++) {
if(max<a[n-1][i])
max = a[n-1][i];
}
System.out.println(max);
in.close();
}
}
즉, a[i][j] += Math.max(a [i-1][j] , a [i-1][j-1]); 과 같은 수식은 가장 작은 문제(가장 낮은 행, 결과로 부터 가장 먼 경우)부터 문제를 고려하기 시작하게 되는데 그 과정에서 필요한 Math.max(a [i-1][j] , a [i-1][j-1])의 값들은 이미 이전부터 저장해 오면서 올라가기 때문에 별도의 dp배열을 사용할 필요가 없다는 의미이다.