Red Salmon

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

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

이 문제는 참 그렇다. 이렇게 많이 틀린 문제가 있엇던가 싶다. 

그래도 이번엔 정답을 맞았다. 1년전에 도전했고 9개월전 6일전 1일전 도전하여 결국 풀어냈는데 생각해보면 이 단순한걸 왜틀렸을까? 왜생각을 못했을까 싶다..

위상정렬이라는것이 필요하다고 하여 공부해보았고 참 요긴하게 쓰이겠구나 했지만, 위상정렬이라는 개념을 모르더라도 DP와 dfs만 안다면 풀 수 있는 문제였다. 

결국은 최장길이를 구하는 문제인데 dfs로 전부 탐색해서 구했다.

풀이는 다음과 같다.

1. 인풋을 입력받지만 나는 벡터에 값을 담을때 반대로 담았다.

2. 찾고자하는 건물번호를 입력을 받으면 그 지점에서부터 시작을 하였다.

3. 그리고 dp[now] 에 값이 있다면 그값을 리턴하고 아니라면 dp[now]에 현재 arr[now]값을 주고 계산을 시작하였다.

그런데 여기서 계산을 한다.

4. 포문을 열고 현재 녀석과 연결된 녀석을 살펴보고 해당녀석을 다시 dfs로 작업을 시작한다.

그럼 결국 여기저기 찾으러 다닐텐데 만약 dp[now] 값이 존재하면 이미 만든 값이므로 그 값을 사용할테고 그값을 사용하면서+val이 크다면 그 구한값에 +val만하여 사용하고 아니면 그냥 쓰는식이다. 

간단한 문제라고 생각되는데 왜이리 해맸는지 모르겠다. 

가만보면 난 이런 dp+dfs에는 알면서 자주틀리는거같다. 나중에 다시풀어보거나 비슷한 문제를 다시 접해봐야겠다. 

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

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

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

        https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/11726.cpp

둘다 DP문제로 어려운 DP가아닌 기초 DP이다. 그냥 숫자놀이에 불과하다. 타일링 문제는 전에 3xn타일링 풀때보다 훨씬 쉬웠고, 동물원은

테스트케이스만들기가 조금 귀찮았었다. 

근데 뭐 너무도 흔한 DP여서 금방풀었다.

이제 이런  DP는 아주 쉽게 풀 수 있게 되었다.

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

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

이 문제역시 DP이다. 근데 참 친절하게 예제가 많다.  그리고 이런 문제는 전형적인 DP유형중의 하나이다. 과거 동전문제를 풀었었는데 그것과 설명만 다를뿐 똑같은 문제이다. 

결국 i일때부터 하나씩 처리하면 되는 문제이다. 뭐 생각도 별로 안한 DP문제인데, 불과 1년전에는 이런문제 풀지도 못했는데 이제는 5분에서 10분정도면 푸는 문제가 되었다. 

역시 알고리즘은 꾸준히 하는게 중요한거 같다.

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

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

이 문제는 딱봐도 DP이다. 그런데 정말 귀찮았다. DP 수식을 만들려면 기본적으로 n이 한 4정도까지는 테스트샘플이 필요한데 

이녀석은 수작업으로하기에 너무나도 많았다. 정말 급증하는 수준이었다.

문제를 보면 홀수일때는 생각할 필요도없이 0이다. 왜냐면 2*1타일로 3*3, 3*5 이런타일은 채울 방법이 없다는것은 누구나 알기 때문이다.

그래서 짝수만 보면 되는데 문제는 예제로 2일때 3이라고 알려줬다. 그래서 나는 4일때 수작업으로 해보니 11이 나왔다.

하지만 3 11 로는 어떠한 수식도 짐작하기 힘들다. 그래서 6일때 얼마인지 구해보기로 했다. 

수작업으로 그려보니 약 10분정도 걸렸고 41이라는걸 알았다.

3 11 41이 나오니 수식이 감이 왔다. 현재 i값에 3배 혹은 4배를 한후 어떤 처리를 했다는 의미인것 같았고, 3배를 할때와 4배를 할때 얼마나 차이있나 봤더니, 4배를 하면 바로 전전수를 빼주면 값이 나온다는 가설이 세워졌고 도전해봤다.

그게 정답이었고, 문제푸는시간보다 손으로 그리는 시간이 훨씬 길었던 문제이다.