[백준]9465_스티커_dp

[문제 링크]

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

9465번: 스티커

 

[생각 흐름]

dp 방법으로 해결하였다

선택할 수 있는 방법이 (1번 줄, 2번 줄) OX, XO, XX 세 가지를 가질 수 있으므로 (O는 스티커가 있다, X는 스티커가 없는 경우)

각 경우에 맞춰서 초기값을 계산하였다.

 

그리고 아래의 코드와 같이 ox-> xx , ox->xo, xx-> ox, xx->xo, xx->xx , xo->ox , xo->xx로 7가지의 경우로 진행할 수 있다. 

그리고 이동한 후 ox -> xx와 xx-> xx, xo -> xx 중 가장 큰 값을 xx 테이블에 넣는 방식으로 마지막 column까지 진행하여

마지막 칸에서 제일 큰 값을 출력해주면 된다.

 

int ox_xx = map1[i-1];
int ox_xo = map1[i-1]+map[1][i];
int xx_ox = map3[i-1]+map[0][i];
int xx_xx =map3[i-1];
int xx_xo = map3[i-1]+map[1][i];
int xo_xx = map2[i-1];
int xo_ox = map2[i-1]+map[0][i];

map1[i]=Math.max(xx_ox,xo_ox);
map2[i] = Math.max(ox_xo,xx_xo);
map3[i] = Math.max(Math.max(ox_xx,xx_xx),xo_xx);

 

 

[코드]

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));
        StringTokenizer st;
        StringBuilder sb= new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            int col = Integer.parseInt(br.readLine());
            int map[][] = new int[2][col];
            int map1[] = new int[col]; //OX
            int map2[] = new int[col]; //XO
            int map3[] = new int[col]; //XX
            for(int i=0;i<2;i++){
                st=new StringTokenizer(br.readLine());
                for(int j=0;j<col;j++)map[i][j] = Integer.parseInt(st.nextToken());
            }
            map1[0] = map[0][0];
            map2[0] = map[1][0];
            for(int i=1;i<col;i++){
                map1[i]=Math.max(map3[i-1]+map[0][i],map2[i-1]+map[0][i]);
                map2[i] = Math.max(map3[i-1]+map[1][i],map1[i-1]+map[1][i]);
                map3[i] = Math.max(map3[i-1],Math.max(map1[i-1],map2[i-1]));


                /*
                //ex) ox -> xx 가 되는 경우의 케이스
                int ox_xx = map1[i-1];
                int ox_xo = map1[i-1]+map[1][i];
                int xx_ox = map3[i-1]+map[0][i];
                int xx_xx =map3[i-1];
                int xx_xo = map3[i-1]+map[1][i];
                int xo_xx = map2[i-1];
                int xo_ox = map2[i-1]+map[0][i];

                map1[i]=Math.max(xx_ox,xo_ox);
                map2[i] = Math.max(ox_xo,xx_xo);
                map3[i] = Math.max(Math.max(ox_xx,xx_xx),xo_xx);
                 */
            }
            sb.append(Math.max(Math.max(map1[col-1],map2[col-1]),map3[col-1])+"\n");
        }
        System.out.println(sb);
    }
}