[白俊]1563号皆勤賞
問題で与えられるのはNだけである.
に出席
問題条件
必要
トラブルシューティング
absは0、1、2
absが2の場合-->現在のabsは使用できません.absは0を超えています.
lateが0の場合-->現在もlateが可能で、late++が超え、absが0を超えています.(連続性が破られたため)
lateが1の場合、-->現在のlateは絶対に不可能であり、元のlate(1)を超えています.
選択可能な場合:lateが0の場合のみ使用可能
absは、absが0,1の場合に選択できます.
Oが選択できる場合:以上の場合も完全に選択できます.
「late」または「O」を選択した場合、-->absは0より大きい必要があります.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static int n;
public static long [][][] cache = new long[1001][2][3]; // total, late, abs 이다. late는 0,1 가능 abs는 0,1,2 가능
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
// Setting cache (value : -1)
for(int i=0;i<cache.length;i++){
for(int j=0;j<cache[0].length;j++){
Arrays.fill(cache[i][j],-1);
}
}
}
public static long dp(int total, int late, int abs){
if(total == n) return 1;
if(cache[total][late][abs]!=-1)return cache[total][late][abs];
long sum = 0 ;
long temp = 0;
// late나 O 선택시, 지각 연속이 깨지는 것이기 때문에 abs에는 0이 오게 된다.
// late는 전체에서 지각이 두 번 이상 있으면 안 되는 것 이기 때문에 , abs나 O를 선택한다고 late를 초기화시키진 않는다.
// late 선택도 가능한 경우
if(late == 0) {
temp = dp(total+1,late+1,0);
sum = proc(temp,sum);
}
// abs 선택도 가능한 경우
if(abs<2) {
temp=dp(total+1,late,abs+1);
sum = proc(temp,sum);
}
// O를 선택하는 경우
temp = dp(total+1,late,0);
sum = proc(temp,sum);
cache[total][late][abs]=sum;
//System.out.println("TOTAL "+total +", late: "+late+", abs: "+abs);
System.out.println("cache[total][late][abs] = " + cache[total][late][abs]);
return sum;
}
public static long proc(long temp, long sum){
temp %=1000000;
sum%=1000000;
return (temp+sum)%1000000;
}
public static void main(String[] args) throws IOException{
Setting();
dp(0,0,0);
System.out.println(cache[0][0][0]);
}
}Reference
この問題について([白俊]1563号皆勤賞), 我々は、より多くの情報をここで見つけました https://velog.io/@ynoolee/백준1563번-개근상テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol