[BOJ] 백준 1563번 개근상 (Java)

#1563 개근상

난이도 : 골드 4

유형 : DP

1563번: 개근상

▸ 문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA LAOO LAOA LAAO

총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

▸ 출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

 

 

문제 풀이 

조건에 따라 dp배열만 잘 설계하면 된다.

개근상을 받기 위해 따져봐야하는 변수는  전체 일 수, 지각 횟수, 결석 횟수로 총 3가지이다. 

 

📝  풀이 메모

1. 함수에 매개변수를 추가하여 모든 재귀에 absent의 수를 달았다.

직접 조건문을 돌려 연속3일을 걸러내는 작업은 필요없어져서 삭제했다.

static int solve(int len, int late, int absent) {
	// 필요없음
	if(status.length()>0 && status.charAt(status.length()-1) != 'A') {
				absent =0;
			}
	// .... 
	dp[len][late][absent] = solve(status+"O", late, absent)
			+ solve(status+"A", late, absent+1)
			+ solve(status+"L", late+1, absent);
}

 

☛ 재귀함수이므로 트리를 뻗어 나가는 과정에서 그냥 status+"A"인 함수에만 absent+1을 해주면 되었다.

dp[len][late][absent] = solve(len+1, late, 0)
				+ solve(len+1, late, absent+1)
				+ solve(len+1, late+1, 0);

 

2. 처음에 일 수를 String으로 다뤘다가 int형으로 변경해주었다. 

직관적으로 풀이를 하다보니 문자열로 "OOAL"이런 식으로 데이터를 받았다. 다 풀고나서 효율성을 위해 int로 변경해주었다. 

 

String 재귀함수

static int solve(String status, int late, int absent) {
		int len = status.length();
		if(dp[len][late][absent] != -1) return dp[len][late][absent];
		if(late > 1 || absent == 3) {
			return 0;
		}
		if(len > n-1) {
			return 1;
		}
		
		dp[len][late][absent] = 0;
		
		dp[len][late][absent] = solve(status+"O", late, 0)
								+ solve(status+"A", late, absent+1)
								+ solve(status+"L", late+1, 0);
		
		return dp[len][late][absent] % DIV;
		
	}

 

int 재귀함수

static int solve(int len, int late, int absent) {
		if(dp[len][late][absent] != -1) return dp[len][late][absent];
		if(late > 1 || absent == 3) {
			return 0;
		}
		if(len > n-1) {
			return 1;
		}
		
		dp[len][late][absent] = 0;
		
		dp[len][late][absent] = solve(len+1, late, 0)
				+ solve(len+1, late, absent+1)
				+ solve(len+1, late+1, 0);
		
		return dp[len][late][absent] % DIV;
		
	}

 

 

 

풀이 코드  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int n;
	static int dp[][][];
	static int DIV = 1_000_000;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		dp = new int[n+1][3][4];
		
		for(int i=0; i<n+1; i++) {
			for(int j=0; j<3; j++) {
				Arrays.fill(dp[i][j], -1);
			}
		}
		
		System.out.println(solve(0, 0, 0));
	}
	
	static int solve(int len, int late, int absent) {
		if(dp[len][late][absent] != -1) return dp[len][late][absent];
		if(late > 1 || absent == 3) {
			return 0;
		}
		if(len > n-1) {
			return 1;
		}
		
		dp[len][late][absent] = 0;
		
		dp[len][late][absent] = solve(len+1, late, 0)
				+ solve(len+1, late, absent+1)
				+ solve(len+1, late+1, 0);
		
		return dp[len][late][absent] % DIV;
		
	}
}