백준 1563 - 개근상

Java

1563 번 - 개근상

문제

접근 방법

탑다운 방식으로 해결한다.
아무것도 없는 빈 문자열에서부터 ‘o’, ‘a’, ‘l’을 하나씩 붙힌다고 가정하고 DFS를 호출한다.
‘a’의 경우 3개 연속되지 않도록, ‘l’의 경우는 2개 이상 나타나지 않도록 조건을 두어 Top-down 을 만든다.

day 일일때 l이 lCnt만큼 반복되었고 A가 ACnt만큼 연속되어 있을 때 dp로 두어 불필요한 반복을 방지한다.
dp[day][lCnt][ACnt]

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;

	static int[][][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	dp = new int[n + 1][2][3];

    	System.out.println(DFS(1,0,0));

    	br.close();
	}
	// dfs 시작
	private static int DFS(int day, int lCnt, int ACnt) {
		if(lCnt == 2 || ACnt == 3)
			return 0;

		if(day > n)
			return 1;
		// 한번 방문하였을 시, 다시 방문하지 않도록 한다.
		if(dp[day][lCnt][ACnt] != 0) {
			return dp[day][lCnt][ACnt];
		}
		// top-down 방식으로 합친다.
		//
		int sum = (DFS(day + 1, lCnt, 0) + DFS(day + 1, lCnt + 1, 0) + DFS(day + 1, lCnt, ACnt + 1)) % 1000000;
		dp[day][lCnt][ACnt] = sum;
		return sum;
	}


	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점