(백준 알고리즘 문제풀이) 10057번 오르막 수

문제

문제 링크

 

문제 접근

• 비트 마스킹을 통해서 문제를 풀어봐야겠다.
• 이 문제 또한 문제의 패턴을 잘 파악해야 한다.
• 내가 생각한 패턴은 표와 같이 생각을 해보았다.
• A[n][0] = 1,
• 일반화 공식: A[n][m] = A[n-1][m] + A[n][m-1]

	0	1	2	3	4	5	6	7	8	9
1자리	1	1	1	1	1	1	1	1	1	1
2자리	1	1 + 1 = 2	2 + 1 = 3	4	5	6	7	8	9	10
3자리	1	3	6	10	15	21	28	36	45	55

코드

import sys

N = int(sys.stdin.readline())
lst = list([1] + [0] * 9 for _ in range(N))
lst[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(1, N):
    for j in range(1, 10):
        lst[i][j] = lst[i-1][j] + lst[i][j-1]

print(sum(lst[N-1]) % 10007)

느낀점

내가 정답을 올바르게 생각은 했지만 조건의 마지막에 적혀져 있는 "첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다."를 생각하지 못하여 시간을 많이 쓴 경험이 있었다. 이로 인하여 조건에 대한 내용도 꼼꼼히 읽으면서 문제풀이를 하면 좋을 것 같다고 느꼇다.

10007을 나누지 못하여 틀림... ㅠ