BOJ 2096
위 문제는 백준 사이트의 알고리즘 2096문제에 관한 설명입니다.
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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 [][] array = new int[N+1][3];
int [][] MAX = new int[N+1][3];
int [][] MIN = new int[N+1][3];
for(int i=1; i<=N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<3; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=1; i<=N; i++) {
MAX[i][0] += Math.max(MAX[i-1][0], MAX[i-1][1]) + array[i][0];
MIN[i][0] += Math.min(MIN[i-1][0], MIN[i-1][1]) + array[i][0];
MAX[i][1] += Math.max(Math.max(MAX[i-1][0], MAX[i-1][1]), MAX[i-1][2]) + array[i][1];
MIN[i][1] += Math.min(Math.min(MIN[i-1][0], MIN[i-1][1]), MIN[i-1][2]) + array[i][1];
MAX[i][2] += Math.max(MAX[i-1][1], MAX[i-1][2]) + array[i][2];
MIN[i][2] += Math.min(MIN[i-1][1], MIN[i-1][2]) + array[i][2];
}
int maxValue = 0, minValue = Integer.MAX_VALUE;
for(int i=0; i<3; i++) {
maxValue = Math.max(maxValue, MAX[N][i]);
minValue = Math.min(minValue, MIN[N][i]);
}
System.out.println(maxValue+" " +minValue);
}
}
이번 문제는 DP로 푸는 문제 였습니다.
3개의 칸에 N개의 층의 값을 넣을 배열이 필요하기 합니다.
여기에 0~9의 값이 임의로 들어갈 것이기에 배열 array [N+1][3]를 선언한 후 값을 넣어줍시다.
최댓값(또는 최솟값)을 담을 배열 MAX[n+1][3], MIN[n+1][3]도 선언합니다.
그리고 최종적으로 나온 최댓값과 최솟값을 저장할 변수 maxValue, minValue을 선언해줍니다.
MAX[i][0] += Math.max(MAX[i-1][0], MAX[i-1][1]) + array[i][0];
MIN[i][0] += Math.min(MIN[i-1][0], MIN[i-1][1]) + array[i][0];
맨 왼쪽(0번방의 값을 저장하는 곳입니다.)은 맨왼쪽과 가운데에서 값이 올 수 있기 때문에
2가지 중 큰 값을 MAX배열에, 작은 값을 MIN배열에, 넣고 array[i][0]를 더 해줍니다.
가운데의 경우
MAX[i][1] += Math.max(Math.max(MAX[i-1][0], MAX[i-1][1]), MAX[i-1][2]) + array[i][1];
MIN[i][1] += Math.min(Math.min(MIN[i-1][0], MIN[i-1][1]), MIN[i-1][2]) + array[i][1];
가운데(1번방의 값을 저장하는 곳입니다.)은 맨왼쪽과 가운데, 오른쪽에서 값이 올 수 있기 때문에
3가지 중 큰 값을 MAX배열에, 작은 값을 MIN배열에, 넣고 array[i][1]를 더 해줍니다.
오른쪽 또한 마찬가지입니다.
int maxValue = 0, minValue = Integer.MAX_VALUE;
for(int i=0; i<3; i++) {
maxValue = Math.max(maxValue, MAX[N][i]);
minValue = Math.min(minValue, MIN[N][i]);
}
그리고 맨 아래에서 하나씩 훑으면서 가장 큰 값과 작은 값만 확인합니다.