목록1562 (1)

이 험난한 세상에서어어~

백준, 계단 수(1562, java)

문제 설명 길이가 N인 계단 수열의 수를 구하는 문제인데, 이때 0부터 9까지의 숫자가 모두 한 번 이상 등장해야 한다. 이때 0으로 시작하는 수는 계단수가 아니다. https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 첫 번째 접근 DP 문제이기 때문에 처음에는 직접 손으로 풀어 써봤다. 이때 계단수의 규칙을 발견했는데, 0혹은 9의 옆 자리에는 1과 8밖에 오지 못한다는 점이다. 일단 0의 경우에는 0과 x를 빼서 절댓값이 1이 되는 경우가 1혹은 -1인데, -1은 오지 못하니 1밖에 없다. 9 또한 10과 8이 있지만, 10은 고려 사항이 아니니 8밖에 오..
algorithm/유형 2023. 7. 29. 15:07
이전 Prev 1 Next 다음