오늘의 문제는 “10844번 쉬운 계단 수”.
어떤 수의 인접한 모든 자리 수의 차이가 1이 날 때, 계단 수라고 하면 길이가 N인 계단 수가 총 몇 개 있는지 구하는 문제이다.
처음에는 어떤 수 N이 주어질 때 숫자 N이 계단 수인지를 판별하는 함수를 만들어야 하나? 라고 고민했지만,
문제의 전체적인 뉘앙스로 봤을 때, 각 숫자별로 판별을 실행하면 시간초과가 날 것 같았다.
그래서 고민하던 중, 어떤 숫자가 계단수이면, 그 숫자의 일의 자리에 따라 다음 계단수가 규칙적으로 생긴다는 사실을 알았다.
예를 들어, 45656이란 계단수가 있으면,
이 계단수에 의해 456565와 456567 두 계단수가 생성된다.
#include <iostream>
using namespace std;
int main()
{
int arr[10];
int nxt[10];
int cnt = 1;
int sum, n;
arr[0] = 0; //일의 자리가 0으로 끝나는 한 자리 계단수 : 0개
arr[1] = 1; //일의 자리가 1으로 끝나는 한 자리 계단수 : 1개
arr[2] = 1; //일의 자리가 2으로 끝나는 한 자리 계단수 : 1개
arr[3] = 1; //일의 자리가 3으로 끝나는 한 자리 계단수 : 1개
arr[4] = 1; //일의 자리가 4으로 끝나는 한 자리 계단수 : 1개
arr[5] = 1; //일의 자리가 5으로 끝나는 한 자리 계단수 : 1개
arr[6] = 1; //일의 자리가 6으로 끝나는 한 자리 계단수 : 1개
arr[7] = 1; //일의 자리가 7으로 끝나는 한 자리 계단수 : 1개
arr[8] = 1; //일의 자리가 8으로 끝나는 한 자리 계단수 : 1개
arr[9] = 1; //일의 자리가 9으로 끝나는 한 자리 계단수 : 1개
cin >> n;
while (cnt < n)
{
nxt[0] = arr[0];
nxt[1] = arr[0] + arr[2];
nxt[2] = arr[1] + arr[3];
nxt[3] = arr[2] + arr[4];
nxt[4] = arr[3] + arr[5];
nxt[5] = arr[4] + arr[6];
nxt[6] = arr[5] + arr[7];
nxt[7] = arr[6] + arr[8];
nxt[8] = arr[7] + arr[9];
nxt[9] = arr[8] + arr[2];
for (int i = 0; i < 10; i++) //각 배열값이 10억 이상일 경우 나머지로 줄인다.
{
arr[i] = nxt[i] % 1000000000;
}
cnt++;
}
sum = arr[0];
for (int i = 1; i < 10; i++) //각 배열값은 10억 미만이기 때문에 다 더하고 나머지 연산을 해도 된다.
{
sum += arr[i];
sum %= 1000000000;
}
cout << sum << endl;
return 0;
}지금 글을 쓰면서 보니 내가 틀린 곳이 명백히 보이지만….
당시에는 당연히 맞다고 생각했다.
하지만 while문 안의 계단수 연산 규칙이 틀렸다.
위의 연산 규칙을 바꾼게 아래 코드인데…
#include <iostream>
using namespace std;
int main()
{
int arr[10];
int nxt[10];
int cnt = 1;
int sum, n;
arr[0] = 0; //일의 자리가 0으로 끝나는 한 자리 계단수 : 0개
arr[1] = 1; //일의 자리가 1으로 끝나는 한 자리 계단수 : 1개
arr[2] = 1; //일의 자리가 2으로 끝나는 한 자리 계단수 : 1개
arr[3] = 1; //일의 자리가 3으로 끝나는 한 자리 계단수 : 1개
arr[4] = 1; //일의 자리가 4으로 끝나는 한 자리 계단수 : 1개
arr[5] = 1; //일의 자리가 5으로 끝나는 한 자리 계단수 : 1개
arr[6] = 1; //일의 자리가 6으로 끝나는 한 자리 계단수 : 1개
arr[7] = 1; //일의 자리가 7으로 끝나는 한 자리 계단수 : 1개
arr[8] = 1; //일의 자리가 8으로 끝나는 한 자리 계단수 : 1개
arr[9] = 1; //일의 자리가 9으로 끝나는 한 자리 계단수 : 1개
cin >> n;
while (cnt < n)
{
nxt[0] = arr[1];
nxt[1] = arr[0] + arr[2];
nxt[2] = arr[1] + arr[3];
nxt[3] = arr[2] + arr[4];
nxt[4] = arr[3] + arr[5];
nxt[5] = arr[4] + arr[6];
nxt[6] = arr[5] + arr[7];
nxt[7] = arr[6] + arr[8];
nxt[8] = arr[7] + arr[9];
nxt[9] = arr[8];
for (int i = 0; i < 10; i++) //각 배열값이 10억 이상일 경우 나머지로 줄인다.
{
arr[i] = nxt[i] % 1000000000;
}
cnt++;
}
sum = arr[0];
for (int i = 1; i < 10; i++) //각 배열값은 10억 미만이기 때문에 다 더하고 나머지 연산을 해도 된다.
{
sum += arr[i];
sum %= 1000000000;
}
cout << sum << endl;
return 0;
}똑같은 실수가 두 개 있을 가능성은 간과하고 하나만 고쳐서 냈다가 한 번 더 틀렸었다.