9663 N-Queen
1019 책 페이지
1019
3726을 인풋으로 넣는다고 하면
3726 -> 3719
{3,7,2} += (a[0]+1). {0~a[0]} +=1
3719 -> 3699
{3,7} += (a[1]+1)*10. {0~a[1]} +=10. {0~9} += (a[1]+1) * 1
3699 -> 2999
{3} += (a[2]+1)*100. {0~a[2]} += 100. {0~9} += (a[2]+1) * 20
2999 -> 999
{1~a[3]} += a[2]*1000. {0~9} += (a[3])*300
제일 큰 자리 빼고는 식이 보인다. 조금 복잡해 보이지만 여러가지 테스트케이스를 디버깅하면서 예외처리만 해주면 잘 돌아간다.
9, 99, 999, 9999,,,,,는 점화식으로 cnt배열을 따로 만들어 입력해놓았다.
cnt[0][] = {0,1,1,1,1,1,1,1,1,1}
cnt[1][] = {9,20,20,20,20,20,20,20,20,20}
cnt[2][] = {189,300,300,,,,,,}
점화식을 발견하기 어렵지 않다.
9663
- | / \(역슬래시) 방향을 bitmask로 표현하여 dp인자로 전달해 들어갈 수 있는 자리에 추가하고 cnt++하는 방식으로 구현했다.
N제한이 15라 가로 2^15, 세로 2^15, 대각선 2^31까지밖에 안된다.
시간 제한이 10초라 N중 for문을 돌려도 상관없을 것 같다.