[JAVA] 백준 24464 - 득수 밥 먹이기

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

n이 주어지면 규칙에 따라 득수가 식당에 가는 경우의 수를 구하는 문제이다.

n의 범위와 출력 양식을 보면 DP로 풀어야할 것 같은 느낌이 든다.

메모이제이션 배열은 두 개를 썼는데, 하나는 굶는 경우의 수를 저장하는 1차원 배열 n+1 칸이고

나머지 하나는 n-1 X 4 의 2차원 배열을 사용해 방문하는 1~4번째 식당의 경우의 수를 각각 저장했다.

1,4번째 식당을 방문한 경우 다음날에 각각 3,4번째 식당, 1,2번째 식당 -> 2개를 방문할 수 있지만 2번째와 3번째 식당을 방문한 경우는 각각 1개의 식당만 방문할 수 있기 때문이다.

이렇게 배열을 선언했더니 모듈러 연산을 굉장히 많이 수행해야했다 ㅠㅠ

n번째 굶는 경우의 수 = n-1번째 식당 방문의 경우의 수

n번째 1번 식당 방문 경우의 수 = n-1번째 3, 4 식당 방문 경우의 수 + n-1번째 굶는 경우의 수(굶은 경우 반드시 식당 방문)
n번째 2번 식당 방문 경우의 수 = n-1번째 4 식당 방문 경우의 수 + n-1번째 굶는 경우의 수
n번째 3번 식당 방문 경우의 수 = n-1번째 1 식당 방문 경우의 수 + n-1번째 굶는 경우의 수
n번째 4번 식당 방문 경우의 수 = n-1번째 1, 2 식당 방문 경우의 수 + n-1번째 굶는 경우의 수

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());
        int[] starve = new int[n+1];
        int[][] visit = new int[n+1][4];
       
        starve[0] = 1;
        visit[0][0] = 1;
        visit[0][1] = 1;
        visit[0][2] = 1;
        visit[0][3] = 1;


        for (int i = 1; i < n; i++) {
            starve[i] = ((visit[i-1][0]+visit[i-1][1])% 1000000007+(visit[i-1][2]+visit[i-1][3]) % 1000000007)% 1000000007;
            int target = starve[i-1];
            visit[i][0] = (((visit[i-1][2]+ visit[i-1][3])% 1000000007)% 1000000007 + target) % 1000000007;
            visit[i][1] = (visit[i-1][3]+ target) % 1000000007;
            visit[i][2] = (visit[i-1][0]+ target) % 1000000007;
            visit[i][3] = (((visit[i-1][0] + visit[i-1][1])% 1000000007)% 1000000007+ target) % 1000000007;
        }
        System.out.println((((starve[n-1] + visit[n-1][0]) % 1000000007+ ((visit[n-1][1] + visit[n-1][2]) % 1000000007))% 1000000007+ visit[n-1][3]) % 1000000007 );

    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }

}

DP는 너무 어렵다.

이렇게 이번주도 마라톤 끝이다!