Red Salmon

출처 : 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/6443

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

그냥 순열놀이이다. 그렇게 어렵지 않은 문제이다. 

입력을 먼저 정렬시키고 순열놀이로 쭉 뽑아내면 된다. 다만, 중복이 있으면 안되는데, 이 부분만 처리해주면된다.

다만 조금 의아한부분이 있다면 내가 직접 구현한 DFS로는 시간초과가 났다. 그래서 STL의 next_permutation()을 사용하니 정답이 나왔다. 내가 만든 DFS에 소모적인 부분이 많다는 말인데... 이건 분명 개선해야할 부분이다.

비록 STL로 정답을 맞았을지언정 현재 내가만드는 DFS에는 낭비 되는 부분이 존재하기에 STL에 있는 next_puermutation의 구조를 분석해봤다. 

http://en.cppreference.com/w/cpp/algorithm/next_permutation

이 사이트를 참조하면 내부 구조에 대해서 알 수있다. 

나는 기본적으로 해당 문자를 사용했는지 안했는지 체크하는 방식으로 DFS를 구성하였다. 그러다보니 동일한 문자일경우 나의  DFS는 알 수 없으므로, 중복이 반드시 생긴다. 아마 이 문제 때문에 시간초과가 발생한듯 하다. 

물론 출력을 제어하기 위해서 맵이나 다른 방법을 통해 기존에 만든 것들을 저장시키고 확인하여 중복을 피할 수 있으나, 어찌 되었든 중복이 발생하기 때문에, 비효율적이라고 볼 수있다.

추후 이런 문제를 피하기 위하여 새로운 DFS방법을 습득할 필요를 느껴 더 공부해봤다.

template
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

위의 방법이 STL에 있는 next_permutation인데, 좀 독특한 방법이라고 생각이 들었다. 확실히 내가 기본적으로 구성하는 방법과는 전혀 다른 방법이었다. 독특한 점은 재귀가 없다는 점이다. 단순히 반복문을 통해서 재귀와 동일한 능력을 만들고있다.

역시 STL은 정말 대단한 것이다.

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

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

문제를 읽어보면 결국 하냐 안하냐 그차이이다. DP와 DFS사이에 고민을 했다. 둘다 방법이 있다. 그런데 이문제에서 주의깊게 봐야할것은 N이 20이다. 즉, DFS로도 충분히 풀 수있다는 것이다.

만약 N값이 30 이상이라면 사실상 DFS로는 가능성이 없으므로  DP로 접근해야한다. 

dp로 푼다면 각 사람별로 기쁨과 소모 체력을 누적시켜가며 최대값을 갱신하는 방식으로 진행해야겠다. 자세한 수식은 더 생각해봐야겠으나 해당문제에서는 DFS로 풀 수 있기 때문에  DFS로 풀었다. 그리고 단순히 선택을 하고 안하고의 차이이므로 전부 계산을 해보면 답이 나온다.

주의해야할점은 체력이 0이 되거나 마이너스가 되면 그어떠한 점수도 얻지 못한다는 점이다.

출처 : 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로 나눠주면 끝나는 문제이다. 더 간단하다.