[알고리즘] 백준 10844 자바 JAVA 동적프로그래밍

 

 

 

public class BaekJoon_16_10844 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());
		long dp[][] = new long[n + 1][10];

		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < 10; j++) {
				if (j == 0)
					dp[i][j] = dp[i - 1][j + 1] % 1000000000;
				else if (j == 9)
					dp[i][j] = dp[i - 1][j - 1] % 1000000000;
				else
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
			}
		}

		long sum = 0;
		for (int i = 0; i < 10; i++) {
			sum += dp[n][i];
		}

		writer.write(sum % 1000000000 + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

 

즉시 풀지 못했던 문제. 2차원 배열까지 생각해내서 해봤는데 자꾸 값이 이상하게 나와서 구글선생님을 참고했다. 풀다가 너무 안풀리면 내려놓는 것도 방법이다... ㅋㅋㅋㅋ 언제나 그렇듯 해답을 보면 바로 머리를 쥐어박지만..

 

중요한 점은 2차원배열을 쓰고 각 자리수마다 0에서 9까지를 고려해야한다는 점이다. 여기서 좀 더 나아가서 전 자리수가 0일때와 9일때는 10과 89 밖에 없으니까 2 ~ 8 일때와 같이 1+1로 카운팅하면 안된다. 이걸 동적프로그래밍으로 구현하면 끝.

 

생각의 전환! 조금 더 키우자.