Red Salmon

출처 : 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이 되거나 마이너스가 되면 그어떠한 점수도 얻지 못한다는 점이다.