백준 결전의 금요일(25194)

DP 문제를 풀었다.

 

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

25194번: 결전의 금요일

 

 

금요일은 작업일%7 이 나머지가 4인경우를 구하면 된다.

 

작업일들의 모든 경우의수를 구하게 처음 구했다 시간초과가 발생되었다.

 

생각 가능한 범주로는 작업일기준으로 월화수목금토일만 관리하면된다.

 

그렇게 발생된 케이스에서 게속 DP를 진행하면된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[] works = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i=0; i < N; i++) {
            works[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[8];
        dp[0] = 1;

        for (int i=0; i < N; i++) {

            int[] temp = Arrays.copyOf(dp, dp.length);
            for (int j=0; j < dp.length; j++) {

                if (dp[j] > 0) {
                    int num = j + works[i];
                    temp[num%7] += 1;
                }
            }
            dp = temp;
        }



        if (dp[4] > 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

}

 

결과