Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/10844.cpp

정말 많은 생각을 하게 한 문제이다.

DP인것은 알았으나 어떤식으로 작성해야할지 정말 감이 오지 않았다.

역시 이럴땐 하나씩 다 해보는것이 최고이다.

나는 N이 1부터 3까지 전부 만들어 보았다. 시작값은 0이 될수없으므로 1부터 시작하여 

가장 앞자리가 1, 2, 3...9 까지 전부 구해보았다. (많은 DP문제가 이런식으로 접근한다.)

이렇게 하고나서 규칙을 찾기 위해 많은 시간을 소모했다. 

결국은 삼각형 구조였는데, 나는 삼각형구조를 생각은 했으나 직각삼각형 구조를 생각하여 쉽게 풀리지 않았던것 같다.

개인적인 경험으로 DP에서 이렇게 배열을 조합해야 한다면 결코 어렵게 풀리지 않으며, 특히 수가 나열된상태에서 찾는것이라면 상하좌우대각선포함해서 1칸씩 움직이는 범위안에 규칙이 존재하는것 같다.

뭐 결국은 풀어서 다행이다.

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

어딜봐도 저길 봐도 그냥 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미만이면 계속 증가시키고 도달하면 다시 감소시키는 식으로 계속 줄여나가서 경우의수를 만들어준다. 

쉬운듯 어려운문제였다.