2096번: 내려가기
(소요시간 : 48분..)
- 처음 숫자 선택 : 3개의 숫자 중 하나를 고른다.
- 첫 줄 → 마지막 줄 까면 끝나는 놀이
- 다음 줄로 넘어 갈 때의 제약 조건
- 바로 아래칸 OR "바로 아래칸에 인접한 칸으로만 "
- 근데 각 줄 당 세개의 칸 만 존재.
- 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하라.
- 점수 = 원룡이가 위치한 곳의 수의 합
- 조건
- N개의 줄, N은 1이상 10만 이하.
- 각 숫자는 0~9 의 정수
풀이 생각 : 첫 번째로 떠오르는 것은 DP
- 왜냐하면, 첫 번 째 줄의 숫자도, 무작정 가장 큰 수나, 가장 작은 수를 선택하면 안된다.
1 2 3 -> 3을 선택
4 0 1 -> 4를 선택할 수가 없다. 또 이 줄의 max인 1선택하면
9 6 1 -> 여기서 또, 9를 선택할 수가 없다.
0 7 8
하나의 선택은 어느 range까지에서의 min, max에 영향? -> 한 줄
// 정답 22 7-
각 줄에서는 index 0,1,2에 있는 것 중 하나를 선택하도록 한다.
-
현재 줄의 index에 +1,0,-1을 선택 할 수 있으며 → 이것이 0보다 작거나 2보다 크면 out of range 이므로 pass한다.
-
전체탐색처럼 생각해 보면, 결국 중복되는 subproblem들이 존재 한다.
이 경우, 첫 줄에서 1을 선택할 때, 두 번째 줄에서 4,0 선택 가능 첫 줄에서 2를 선택할 때, 두 번째 줄에서 4,0,1 선택가능. 결국 다음 줄에서 선택한 것은 그 다음줄에만 영향을 주니 subproblem이 생긴다. 이를 top down 방식으로 생각하되, 이미 방문한 것을 재방문 하지 않도록만 해 보자. 1 2 3 4 0 1 9 6 -
min 과 max 에 대한 것을 따로 해야하기 때문에, cache는 3차원으로 생성하였다.
-
이미 해당 좌표에 대한 min 을 구하기 위한 여정을 떠났다면( min을 구하기 위한 과정에서 해당 좌표를 이미 방문) 다시 방문 할 필요가 없다.
-
이미 해당 좌표에 대한 max 를 구하기 위한 여정을 떠났다면( min을 구하기 위한 과정에서 해당 좌표를 이미 방문) 다시 방문 할 필요가 없다.
-
재귀함수를 사용하는 방식의 DP는 잘 생각나는데, 그 외의 것을 계속해서 못 해내고 있다.. 그래서 bottom up 방식으로도 다시 하나 짜 보았다.
top down approach
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static int[][] board = new int[100000][3];
public static int[][][] cache = new int[100000][3][2];
public static boolean[][][] visit = new boolean[100000][3][2];
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
for(int c=0;c<3;c++){
board[i][c] = Integer.parseInt(st.nextToken());
}
}
// setting cache
for(int r=0;r<n;r++){
for(int c=0;c<3;c++)
Arrays.fill(cache[r][c],-1);
}
}
// max 에 대해, min 에 대해 각각 해도 될 것 같다.
// max는 cahce[r][c]의 0에 , min 은 1에 저장
// target은 지금 구하는게 max인지 min인지를 나타낸다.
public static int dp_max(int y,int x){
if(y==n-1) return board[y][x];
if(cache[y][x][0]!=-1)return cache[y][x][0];
int ny=y+1,nx=0,max=0;
for(int idx=-1;idx<2;idx++){
// curx + idx
nx = x +idx;
if(nx<0||nx>2) continue;
max = Math.max(max,dp_max(ny,nx));
}
max += board[y][x];
return cache[y][x][0]=max;
}
public static int dp_min(int y, int x){
if(y == n-1) return board[y][x];
if(cache[y][x][1]!=-1) return cache[y][x][1];
int ny =y+1,nx=0,min = Integer.MAX_VALUE; // 9 * 100000 = 90만
for(int idx=-1;idx<2;idx++){
nx = x +idx;
if(nx<0 || nx>2) continue;
min = Math.min(min,dp_min(ny,nx));
}
min += board[y][x];
return cache[y][x][1]=min;
}
public static void main(String[] args) throws IOException {
Setting();
int max=0,min=Integer.MAX_VALUE;
for(int idx=0;idx<3;idx++){
min = Math.min(min,dp_min(0,idx));
max = Math.max(max,dp_max(0,idx));
}
System.out.println(max+" "+min);
}
}bottom up 방식
-
for문을 사용한다.
-
공간 복잡도를 최소화 하기 위하여, cache 배열을 사용하지 않고, min, max 변수를 for문을 도는 동안 update하는 방식을 사용할 수 있다.- -> 각 column에 대한 min, max를 각 row를 진행해 나가면서 update 해 나가야 한다.
- update란 자고로.. for문을 반복하며 현재값이 이전값이 되므로, int[3][2] 짜리의 min, max 배열을 사용한다.
-
r행 c열 에 대해 구할 때, r-1행 c-1열 , r-1행 c열, r-1행 c+1열 에 더하는 것 중 가장 max값 , 또는 min 을 update한다.
package coding;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static int[][] board = new int[100000][3];
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine());
for(int c=0;c<3;c++){
board[i][c] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws IOException {
Setting();
bottomUp();
}
private static void bottomUp() {
// 마지막에 이 셋 중 max -> real max
// 마지막에 이 셋 중 min -> real min
// mins[r][0] 은 pre (이전 row)
// mins[r][1] 은 cur (현재 row)
int[][] mins = new int[2][3];
int[][] maxs = new int[2][3];
// INIT
for(int c=0;c<3;c++) {
mins[0][c] = board[0][c];
maxs[0][c] = board[0][c];
}
// SOLVE
for(int row=1;row<n;row++){
// mins,max[0]을 구하기 위해서는 -> c와 c+1을
mins[1][0] = Math.min(mins[0][0],mins[0][1])+board[row][0];
maxs[1][0] = Math.max(maxs[0][0],maxs[0][1])+board[row][0];
// mins,max[1]을 구하기 위해서는 -> c-1과 c와 c+1을
mins[1][1] = Math.min(mins[0][0],mins[0][1]);
mins[1][1] = Math.min(mins[1][1],mins[0][2]) + board[row][1];
maxs[1][1] = Math.max(maxs[0][0],maxs[0][1]);
maxs[1][1] = Math.max(maxs[1][1],maxs[0][2]) + board[row][1];
// mins,max[2]를 구하기 위해서는 -> c-1과 c를
mins[1][2] = Math.min(mins[0][1],mins[0][2]) + board[row][2];
maxs[1][2] = Math.max(maxs[0][1],maxs[0][2]) + board[row][2];
// 다시 pre와 cur을 바꾼다.
for(int c=0;c<3;c++){
mins[0][c]=mins[1][c];
maxs[0][c]=maxs[1][c];
}
}
// 셋 중 최대 최소 값을 구한다.
int resmax=0,resmin = Integer.MAX_VALUE;
for(int c=0;c<3;c++){
resmax = Math.max(resmax,maxs[0][c]);
resmin = Math.min(resmin,mins[0][c]);
}
System.out.println(resmax+" "+resmin);
}
}