반응형
이 문제는 다이나믹 프로그래밍을 이용하여 이전의 최선의 경우의 수를 배열에 저장하며 푸는 문제입니다.
코드를 보면서 이 문제를 설명해드리겠습니다.
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] intArr = new int[n][];
for(int i = 1; i<=n; i++)
intArr[i-1] = new int[i];
for(int i = 0; i<n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j<i+1; j++)
intArr[i][j] = Integer.parseInt(st.nextToken());
}
for(int i = 1; i<n; i++){
for(int j = 0; j<i+1; j++){
if(j == 0)
intArr[i][j] += intArr[i-1][j];
else if(j == i)
intArr[i][j] += intArr[i-1][j-1];
else
intArr[i][j] += Math.max(intArr[i-1][j], intArr[i-1][j-1]);
}
}
int max = Integer.MIN_VALUE;
for(int i = 0; i<n; i++)
max = Math.max(max, intArr[n-1][i]);
System.out.println(max);
}
}
저는 이 문제를 intArr에 처음에는 입력받은 값들을 넣었다가 반복문을 통해서 이전에 있던 값들 중에서 최선의 결과에
도달하게 문제를 풀었습니다.
그림을 통해서 알고리즘을 설명드리겠습니다.
예제 1번을 문제대로 표현한 그림입니다.
문제에서는 값을 입력할 때 왼쪽 대각선에 있는 수를 바로 아래에, 오른쪽 대각선에 있는 수를 우측 하단에 두었습니다.
이 그림을 배열에 들어가 있는 모양대로 보기 편하게 바꿔보도록 하겠습니다.
이와 같은 모양이 됩니다.
따라서 우리는 문제의 조건인 대각선에 있는 것만 선택할 수 있다고 할 때 배열상에서는 바로 아래에 있는 수 또는 우측 하단에 있는 수를 선택할 수 있습니다.
예를 들어 빨간색 블럭이 수를 선택할 때 주황색 블록만 선택할 수 있습니다.
for(int i = 1; i<n; i++){
for(int j = 0; j<i+1; j++){
if(j == 0)
intArr[i][j] += intArr[i-1][j];
else if(j == i)
intArr[i][j] += intArr[i-1][j-1];
else
intArr[i][j] += Math.max(intArr[i-1][j], intArr[i-1][j-1]);
}
}
이 코드는 그것을 나타낸 코드입니다. j가 0일 때이나 j == i일 때를 따로 신경 써 준 이유는 j가 0일 때 j-1의 값을
불러올 수 없기 때문이고 j == i일 때도 마찬가지로 범위를 넘어가서 값을 불러올 수 없기 때문입니다.
반응형
'알고리즘 > 다이나믹 프로그래밍' 카테고리의 다른 글
백준 9251번 : LCS java (0) | 2022.06.02 |
---|---|
백준 12865번 : 평범한 배낭 java (0) | 2022.06.01 |
백준 1149번 : RGB거리 java (0) | 2022.05.27 |
백준 9465번 : 스티커 java (0) | 2022.05.26 |
백준 11660번 : 구간 합 구하기 5 java (0) | 2022.05.25 |
댓글