백준 14677 JAVA : 병약한 윤호

문제

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

14677번: 병약한 윤호

 

풀이 예상

dp 배열로 start, end 지점에서 방문한 적이 있다면 메모를 해 두고, 또 방문 했을 때 바로 꺼내서 쓸 수 있도록 했다.

메모를 하지않으니까 시간초과가 났고, 메모를 하니까 통과할 수 있었다.

 

풀이방법 (접근 방법 & 시간복잡도)

B:0, L:1, D:2 로 저장 해 두고, 시작점과 끝점, 먹어야할 것을 들고 다니면서 갱신해준다.

지금 먹어야 할 약이 start 부분이나 end 부분에 있다면 범위를 바꾸고, 먹어야 할 약 숫자를 바꿔서 dfs로 찾는다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int[] arr;
    static int[][] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N*3];
        dp = new int[N*3][N*3];
        String str = br.readLine();
        for (int i = 0; i < 3*N; i++) {
            char c = str.charAt(i);
            if(c == 'L') {
                arr[i] = 1;
            }else if(c == 'D') {
                arr[i] = 2;
            }
        }
        for (int i = 0; i < 3*N; i++) {
            for (int j = 0; j < 3*N; j++) {
                dp[i][j] = -1;
            }
        }

        System.out.println(check(0, 3*N-1, 0)); //시작점, 끝점, 먹어야할것

    }
    static int check(int start, int end, int need) {
        if(start > end) return 0;
        int answer = dp[start][end];
        if(answer != -1) return answer; //이미 방문한 적 있다면 리턴

        answer = 0;
        if(arr[start]%3 == need%3) {
            //먹어야 할 약 이면
            answer = Math.max(answer, check(start+1, end, need+1)+1);
        }
        if(arr[end]%3 == need%3) {
            answer = Math.max(answer, check(start, end-1, need+1)+1);

        }
        dp[start][end] = answer; //기록
        return answer;
    }
}

 

결과