백준(BOJ) 12849: 본대 산책

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

매우 상징성이 강한 문제다. 내가 그동안 왜 안나오나... 하고 생각했던 그런문제다. 문제가 조건을 명확하게 주지 않은 면이 있는데, 출발점도 정보관이고 도착점도 정보관으로 놓고 푸는 문제다.

문제에서 묻는것은 출발점에서 시작해 D분이 지났을때 다시 출발점으로 돌아올수 있는 경로의 수이다. 이렇게 총 경로의 수를 구할때 Dynamic programming으로 해결할 수 있음을 유의하자! 

정석은 2차원배열을 이용하는 것이지만 배열을 하나더 추가로 두는 조건으로 1차원 배열 2개로도 해결이 가능하다. 두 풀이 모두 소개한다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    /*
        정보과학 0
        전산 1
        미래 2
        신양 3
        한경직 4
        진리5
        형남 6
        학생회 7
     */
    public static void solution(int d) {
        long[][]dp=new long[d+1][8];
        dp[0][0]= 1;
        for(int i=1;i<=d;++i) {
            dp[i][0] = dp[i - 1][1] + dp[i - 1][2];
            dp[i][1] = dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3];
            dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4];
            dp[i][3] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4] + dp[i - 1][5];
            dp[i][4] = dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][5] + dp[i - 1][6];
            dp[i][5] = dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][7];
            dp[i][6] = dp[i - 1][4] + dp[i - 1][7];
            dp[i][7] = dp[i - 1][5] + dp[i - 1][6];
            for (int j = 0; j < 8; ++j)
                dp[i][j] %= 1000000007;
        }
        System.out.println(dp[d][0]);
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int d = Integer.parseInt(br.readLine());
        solution(d);
    }
}

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    /*
        정보과학 0
        전산 1
        미래 2
        신양 3
        한경직 4
        진리5
        형남 6
        학생회 7
     */

    public static void solution(int d) {
        long[] dp = {1, 0, 0, 0, 0, 0, 0, 0};
        for (int i = 0; i < d; ++i) {
            long[]result=new long[8];
            result[0]=dp[1]+dp[2];
            result[1]=dp[0]+dp[2]+dp[3];
            result[2]=dp[0]+dp[1]+dp[3]+dp[4];
            result[3]=dp[1]+dp[2]+dp[4]+dp[5];
            result[4]=dp[2]+dp[3]+dp[5]+dp[6];
            result[5]=dp[3]+dp[4]+dp[7];
            result[6]=dp[4]+dp[7];
            result[7]=dp[5]+dp[6];
            for(int j=0;j<8;++j)
                result[j]%=1000000007;
            dp=result;
        }
        System.out.println(dp[0]);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int d = Integer.parseInt(br.readLine());
        solution(d);
    }
}