Red Salmon

문제  : 코드그라운드 좋은수

정답 : 링크

버전을 2개나 만들었다. 첫번째 버전은 이유는 모르겠으나 0점이 나와서 알고리즘 전체를 변경하기로 하였다.

방법 자체는 동일하다.

먼저 코드그라운드 문제의 특징은 테스트케이스가 여러개인데 이 모든게 제한시간내에 작동해야한다.

BOJ의 경우 케이스당 제한시간인거와 비교하면 다른 방식이다. 

물론 ACM-ICPC도 코드그라운드와 동일하다. 대신 제한시간이 보통 3초이다.

문제의 기본 틀은 다음과 같다.

1. 먼저 2중포문을 통해 숫자 2개의 합을 구한다.  chk 배열을 만들고 체크한다.

2. 현재수 = 이전 3개의 수의 합이다. 즉, 어떤 수 + 1에서 구한 2개의 수가 현재수와 같다면 이는 가능한 경우로 본다. 이 처리를 chk[현재수 - 어떤수]가 참이라면 가능한것이다. 

이 기본틀만 유지하면 된다. 이를 가지고 어떻게 코딩하든 답은 나와야 하는것이다. 틀렸다면 뭐 예상치못하는 문제가 있는것일거라고 생각한다.

그래서 나는 다음과 같은 로직을 세웠다.

1. 40만의 배열을 만든다. (한개 수의 입력 최대는 절대값 10만이다. 음수까지고려하면 20만이되고 나는 2개 수의 합을 구하려 하기 때문에 최대 40만이 된다는 가정을 둔다.)

2. 입력 포문을 만들고 바로 아래 합이 가능한지 확인하는 포문을 둔다. 확인은 다음과 같다. 
    chk[200000+arr[i]-arr[k]]이다. 20만은 쉽게 생각해 0이라고 보면 된다. 이게 음수가 될 수 있기 때문이다. 이는 결과적으로 현재수에 어떤수를 뺐는데 그 수가 이미 체크가 되어있다면 2개의 수로 만든 경우가 되는 것이다. 그러므로 ++를 해주고 바로 브레이크 처리를 한다. 중복을 피해야하기 때문이다.

3. 2개의 수의 합을 체크하는 포문을 하나 둔다. i도 포함을 해야 한다. 중복으로 더할수도 있기 때문이다.

이렇게 쓰니 참 간단한데, 생각하기 까지 참 오래시간이 걸렸다. 너무오랜만에 코딩을 한 것같다.

출처 : 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/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은 정말 대단한 것이다.