백준11057 C언어

오늘은 비가 온다.. 날씨가 많이 춥다. 저녁에는 영상 10도까지 내려갔다.

오우!! 요즘 반팔만 입고 다녔는데 갑자기 추워졌다.

이런 날씨에 감기 조심해야겠다. 

흠.. 나중에 어떤 일을 하고 살아야 할까.. 잘 모르겠다. 사는게 어렵다~~ 힘들기보단 어려운게 많은 것 같다.

대학교 다닐 때 그냥 교육과정만 따라서 공부하면 끝이였다.

(학교 교육과정은 지금 생각하면 거의 대다수의 사람이 따라 갈 수 있도록 만든게 대단하다..)

근데 대학교 공부는 쉽지 않고~ 미래에 대한 고민? 보증금? 경제? 주식? 재테크? 연애? 등등 내가 잘 모르는게 너무 많다. 

그래서 그런지 왠지 모를 막막함에 숨이 막히고 우울해지는 요즘이다. 미래가 두렵달까.. 

그래도 뭐든지 step by step이다. 한 걸음 한 걸음 가다 보면 답이 보이지 않을까? 아무튼 각설하고, 문제를 보자

 

 

 

처음에는 왔더 헬~~ 경우의 수가 많은데 어떻게 규칙 구함? 이렇게 막막했는데 하나씩 적다 보니까 규칙이 보인다.

아아... 영감이 보인다... 그래서 다 적다보니까 아래와 같은 점화식이 얼추 만들어졌다.

ㅊㅓ

 

 

 

 

이를 코드에 적용하면 이렇게 된다~~

#include<stdio.h>

int main() {

	int arr[1001][10] = { 1, 1, 1, 1, 1, 1,1 , 1, 1,1 };
	int sum = 0;
	int n;

	scanf_s("%d", &n);

	for (int i = 1; i < n; i++) {
		for (int k = 0; k < 10; k++) {
			for (int g = k; g < 10; g++) {
				arr[i][k] = (arr[i][k] + arr[i - 1][g])%10007;

			}
		}
	
	}
	
	for (int i = 0; i < 10; i++)
		sum = (sum + arr[n-1][i])%10007;

	printf("%d", sum);


	return 0;
}

 

 

흠.. DP문제는 겁 먹지 말고 규칙 찾는게 좋은 것 같다~