[AC] 1562 계단 수

출처 : https://www.acmicpc.net/problem/1562

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1562.cpp

어딜봐도 저길 봐도 그냥 DP가 아니면 답이 나오지 않을 문제이다.

그리고 숫자 10개를 활용해야한다. 이런문제는 대게 비트연산을 필요로한다.

문제는 0~9까지 모든 수를 활용 하여야 하며 계단식으로 수가 배치되어야 한다. 즉 n번째 수와 n-1 그리고 n+1은 각각 1씩만 차이가 나야한다는 말이다.

이 문제의 접근 방법은 조금 까다롭다. 타인의 힌트를 보지 않았다면 풀지 못했을것 같다. 아직은 공부가 많이 필요하다.

접근방법

1. 먼저 시작값이 0은 아니니 1부터 9까지 돌린다고 가정하고 포문을 돌린다. 

2. 재귀함수를 만드는데 이 함수의 목적은 1부터 n값까지 시작값을 기준으로 길이가 n이될때까지 모든 경우를 만들어보고 이 경우가 조건에 충족을 시키는지 확인하는 용도가 되야 한다.

문제의 접근 방법은 다음과 같다. 여기까지만 이해하면 문제를 풀 수 있다.

코드에서 사용한 부가적인 부분을 설명하자면

int dp[105][10][1 << 10];

이렇게 dp함수를 3차로 만든 이유는 처음 105는 n값이 최대 100이라고 하였기 때문에 누적을 위해서 크게 잡아놨고, 

두번째 10은 각 n번째 수에 대하여 1로시작했을때 2로시작했을때 등등 각 시작값에 대한 경우의 수를 담고 있다.

세번째 표기한 1<<10은 비트연산을 위한 수로써 0~9까지 수들이 전부 사용되고 있는지 체크하기 위함이다.

코드상에서 이문제의 핵심은 12번줄과 13번줄인데, 각각 10미만이면 계속 증가시키고 도달하면 다시 감소시키는 식으로 계속 줄여나가서 경우의수를 만들어준다. 

쉬운듯 어려운문제였다.