BOJ 10844. 쉬운 계단 수

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

이번 문제는 수가 굉장히 커져서 곤란했던 문제다.

 

풀이 방법은 다음과 같이 세가지 방법이 존재한다.

1. 2중 반복문으로 n의 범위 내에서 계단수인지 판별. O(n**2) = 1000000000**2

2. BFS O(n) = 1000000000

3. DP O(n) = 100*10

 

1번과 2번의 경우 n이 무려 10의 100승까지도 될 수 있어 시간이 매우 모자라게 된다.

그러나 3번의 경우는 무려 약 1000번의 연산으로 해결할 수 있다.

 

BFS 풀이 (시간 초과)

n이 합리적인 범위로 주어질 경우에는 유효한 풀이 방법이다.

1의 자리부터 시작하여 유효한 계단 수를 n번째 자리까지 찾아가는 연산이다.

즉 1로 시작하면 그 다음에는 12, 10이 가능하고

12에서는 123, 121이 되며 10은 101이 된다.

실제로 계단 수들을 구해야 할 경우 이 방법을 사용하면 된다.

그러나 여기선 n이 너무 커서 좋지 않다.

DP 풀이

계단수를 조금 살펴보면, 1은 10과 12가 되지만, 0은 01로만 되고 9는 98만 된다.

즉, 이전 계단수에서 앞에 1을 붙여서 계단수가 되려면

이전 계단수가 맨 앞이 0일때와 2일때의 경우의 수를 합한 것과 같다.

즉 이를 활용해 앞자리가 n일때의 계단수 배열을 만들어보면 다음과 같다.

세로축은 n의 값, 가로축(y)은 앞자리의 숫자다.

이처럼 n-1 배열에서 y-1과 y+1의 값을 더하면 [n][y]의 값을 구할 수 있다.

시간초과 난 것은 BFS로 풀이한 것이고

틀린건 마지막에 답을 낼 때 무지성으로 sum(res[1:10]) 했다가 mod c를 안해줘서 overflow가 났다.