Red Salmon

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

쉬운듯 어려운문제였다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2240.cpp

이 문제 역시 DP로 풀 수있다. 처음에는 DFS가 될까? 생각하였지만 아무리 계산해봐도 시간복잡도에서 초과가 되어버린다. 왜냐면 T가 1000이기 때문에 DFS로는 가망성이 없다.

그럼 결국  DP인데, 매 초마다 최대값을 갱신하는 방식을 써야겠다. 

개인적으로 상당히 고생했던 DP이고 결국 풀지못하여 다른사람의 아이디어를 참조했다.

이 DP문제의 경우 숫자로 가지고있는 패턴은 당연히 없고(n이 몇일때 몇이다가 아니다.), 배열로 맞추는 패턴도 아닌것같기 때문이다.

정답자의 아이디어를 빌리면 다음과 같다.

1. 나무의 위치를 입력받음에 따라 스텝수에 따라 해당 위치값을 1씩 더해준다. (이동할수있는 만큼 계속 이동한다고 전제하면 현재 위치에서 얻은 값은 계속 가져갈수있다.)

2. 현재 위치에서 바로 전의 단계에서 옆나무의 포인트를 보고 큰값을 대입한다. (이동을 안 할수도있는것이다.)

3. 최종적으로 담겨있는 가장 큰 값을 출력한다.

참으로 심플한 아이디어이다.  이렇게하면 각 스텝별로 얻을수있는 최고점수를 바로 알 수있다. 정말 신박한 아이디어라고 생각한다.

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

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.02/4811.cpp

dp다. 문제 설명에 있는 h와 w는 중요하지 않다. 그냥 경우의수만 따지면 되는 것이다. 그리고 n이 30일때 엄청 큰수가 나왔지만 long long으로 커버가 되는 수이다. 즉 배열을 long long으로 만들어야 한다.

dp는 언제나 그렇지만 먼저 순차적으로 만들어 봐야한다. 예제를 표현하면 다음과 같다.

이렇게 구성이 되는걸 알 수있으며 우리는 5를 구하는 수식을 찾고 그 수식으로 구한 값으로 6을 추론하여 132가 나온다면 정답을 찾은것이다.

먼저 배열의 순서를 가지고 수열을 만들어 보려고 했으나 어떠한 방법을 사용해도 나오지 않았다. 그러면 이제 배열을 통해 추론해봐야한다.

보통의  DP는 단순 수식이 아니라면 배열의 위치값을 가지고 답을 구하게 하는 경우가 대다수이다. 이문제도 똑같다. 이것저것 역시 노가다를 뛰다보면 다음과 같은 규칙성을 찾을 수 있다.

이 그림은 정답을 말하는것과 같다. 현재 인덱스에서 아래녀석과 오른쪽 녀석에 +1씩 더해준다. 그리고 그과정을 계속 되풀이하면 최종적으로 m번째 원소는 arr[m][m] 을통해서 구할 수 있다. 문제는 0이들어오기전까지 계속 입력을 받으므로 미리 30x30배열을 만들어 값을 다 저장시키고 그 해당값만 출력하게 하면 되는 것이다.

dp를 나도 잘 하지는 못하지만 결국은 결과값들을 가지고 수식을 만들어보고 수식에는 대체적으로 감산이없으며 만약 찾을수 없을 경우에는 위와같이 배열을 펼쳐서 생각하다보면 결국 뭔가 나온다는 것이다.

그리고 드는 생각인데... dp도 결국 많이 풀어보면 순자들의 패턴만 보고도 어느정도 유추할수있을것같다. 왜냐면 dp가 낼수있는 패턴은 거의 정해져있다는 느낌이 많이 든다.

나 역시 이정도로 많이 풀어보진 않았지만 더 풀어서 경지에 오르도록 해야겠다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/1793.cpp

이제 이런문제는 보면 DP구나 하고 느낌이 온다. DP문제는 기본적으로 몇가지 틀이 있다. 이건 내가아는 틀중에 하나였다.

먼저 인풋을 보면 인풋이 200일때 엄청나게 긴 수가 나온다는 것을 알 수 있다. 즉, 문자열로 처리를 해야한다.

dp 는 무조건 처음 5~8개의 데이터는 직접 구해봐야한다.

이 문제의 경우 8일때 171인데 엄청나게 많은 경우의 수이므로 1~5까지 구하는 것을 목표로 삼고 모든 경우의 수를 구해봐야한다.

5까지 구해보면 다음과 같이 구성이 된다. 여기서 규칙을 찾아보면 되는데, 기본적으로 DP는 곱해보고 더해봐야한다.

그리고 보통 현재 데이터에서 최대 3개정도안에 규칙성을 가지고 있는데, 3번째 데이터를 기준으로 f(n-2)*2+f(n-1)이라는 규칙을 찾을 수있다. 물론 찾기까지 시간이 조금 걸렸다.

그외에는 이런식의 규칙이 이루어지고 있으므로 이를 구현하면 끝나는 문제이다.

https://www.acmicpc.net/problem/11727

똑같은 문제이며 그냥 10007로 나눠주면 끝나는 문제이다. 더 간단하다.