boj 14450 Hoof, Paper, Scissors (Gold)

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

14450번: Hoof, Paper, Scissors (Gold)

가위바위보 마지막 문제입니다.

이 문제에서도 입력으로 상대방의 race가 주어지며, 베시는 같은 것만 여러번 연속으로 낼 수 있습니다.

Silver 문제와 다른 점은 K번까지 바꿀 수 있으며, K의 최대는 20입니다.

 

누적합으로는 해결할 수 없으며, dp와 재귀를 활용합니다.

dp[idx][cnt][race]: idx번째 게임에서 베시는 race를 cnt번 변경한 상태고, 현재 race를 낸 상태일 때 얻을 수 있는 최대 점수

3중 배열을 사용해야 하며, 첫 번째 게임에서 race를 낼 수 있는 경우 3가지를 모두 확인해야 합니다.

(race를 인덱스로 활용하고, 편의를 위해 입력에서 race를 숫자로 변경하였습니다.)

 

모든 경우에서 race를 변경하지 않고 연속으로 내는 경우를 구할 수 있고,

cnt < K인 경우에만 race를 변경하는 경우를 구하도록 합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX_N = 100001;
    private final static int MAX_K = 21;
    private static final int RACE_CNT = 3;
    private static int list[] = new int[MAX_N];
    private static int dp[][][] = new int[MAX_N][MAX_K][RACE_CNT];
    private static int N, K;
 
    private static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
    }
 
    private static int getScore(int x, int y) {
        if (x == 0 && y == 1) {
            return 1;
        } else if (x == 1 && y == 2) {
            return 1;
        } else if (x == 2 && y == 0) {
            return 1;
        } else {
            return 0;
        }
    }
 
    private static int dfs(int idx, int cnt, int race) {
        if (idx > N) {
            return 0;
        }
        if (dp[idx][cnt][race] != -1) {
            return dp[idx][cnt][race];
        }
 
        dp[idx][cnt][race] = dfs(idx + 1, cnt, race) + getScore(race, list[idx]);
        if (cnt < K) {
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 1) % RACE_CNT) + getScore(race, list[idx]));
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 2) % RACE_CNT) + getScore(race, list[idx]));
        }
 
        return dp[idx][cnt][race];
    }
 
    private static void func() {
        init();
        System.out.println(Math.max(dfs(1, 0, 0), Math.max(dfs(1, 0, 1), dfs(1, 0, 2))));
    }
 
    private static int getRace(char x) {
        if (x == 'H') {
            return 0;
        } else if (x == 'S') {
            return 1;
        } else {
            return 2;
        }
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = getRace(st.nextToken().charAt(0));
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}