🤍I [백준 10844/C++] 쉬운 계단 수

BOJ 문제 보기

아직 열심히 배우는 단계입니다!🐣☘️
개선점 안내 혹은 잘못된 부분 지적, 질문 모두 환영합니다. 다양한 조언은 부족한 지식을 보완하는데 정말 큰 도움이 됩니다.🥰

---

1. 문제

DP를 활용해 문제를 풀 수 있다. 문제에서 제시한 수 45656의 길이가 1 증가한다면 1의 자리 수에 6과 인접한 수가 들어가야 한다(456565와 456567). 이 원리대로 문제를 해결해보자!

---

2. 해결 과정

계단 수가 어떻게 늘어나는지 바로 이해하기 어려워 자릿수마다 계단 수가 만들어지는 총 개수를 표로 정리했다.

음…ㅎㅎ 앞으로 이렇게는 생각하지 말자. 규칙을 찾기

N마다 계단 수가 9, 17, 32, 61 … 으로 늘어나는 것을 확인할 수 있다.

N=1을 먼저 생각해보자. 0은 제외하고 1부터 9까지 계단 수가 한 개씩 만들어진다.

N=2일 때, 1의 자리 수가 0인 수는 10 하나가 있다. 1의 자리 수가 1인 수는 21이 있고, 2인 수는 12, 32가 있다.

N=3 일 때, 1의 자리 수가 0인 수는 210, 1인 수는 101, 121, 321이다.

N=3에서 만들어지는 수가 N=2와 어떤 관계가 있는지 확인해보자.

N/1의 자리 수	0	1	2
2	10	21	12, 32
3	210	101, 121, 321	212, …

1의 자리 수 0은 인접 수인 1이 N=2에서 21 하나를 만들어 N=3에서 210이 만들어졌다.

1의 자리 수 1은 인접 수인 0이 N=2에서 10을, 2가 12, 32를 만들었다. => N=3에서 만들어진 수: 101, 121, 321

N-1에서 인접한 수들이 만든 숫자 뒤에 현재 1의 자리 수를 붙이면 계단 수가 만들어진다.

자릿수 N과 각 1의 자리 수에서 각각 새로 만들어지는 계단 수.

표로 그려보면 이해하기 쉽다.

1의 자리 수를 D라고 할 때 N-1 자릿수에서 D-1과 D+1을 더한 수가 N 자릿수에서의 D가 된다. 단, D=0일 경우 D+1만 존재하고, D=9일 경우 D-1만 존재하므로 두 숫자는 예외 처리를 한다.

---

3. 코드

자릿수와 1의 자리 수에 맞는 2차원 배열을 만들어 해결할 수 있다.

총 $10^{N}$번 반복하니 수가 커진다. 반복문마다 mod로 나머지를 구하거나 long long자료형을 사용해 문제를 풀어야 한다.

---

4. 생각 정리

처음 문제를 보고 N=4까지의 계단 수 개수를 다 찾았다. 왜 그랬을까 … 경우를 다 찾지 말고 규칙을 찾아 코드로 작성하자.🥲

문제에 생소한 개념이 나오면 곧장 이해하지를 못한다. 이번 문제도 풀이 과정까지 생각해내는 데 한참 걸렸다. 문제를 풀고 나서 다른 분들의 풀이를 확인해보니 다행히 다 비슷한 듯! 큰 수가 들어오면 나머지를 구해 연산하거나, 자료형마다 어느 정도의 숫자가 들어올 수 있는지 가늠할 줄 알아야겠다.