[C++ HackerRank 코드 챌린지] 0-3. Jumping on the Clouds

계속해서 HackerRank에 있는 interview-preparation-kit에 속한 문제중 Jumping on the Clouds에 관해 풀어보도록 하겠습니다.

저의 코드는 github에 올려 두었으니 참고하시면 좋겠습니다.

이 문제는 0과 1의 숫자 array를 입력으로 받고 그 입력 중 0을 연결해서 array의 마지막 항까지 도달할때 이동한 횟수를 구하는 문제입니다. 이때 array는 최대 2칸까지 이동할 수 있습니다.

예를들어서 다음과 같이 사이즈가 7인 array 입력이 들어오면,

7
0 0 1 0 0 1 0

1-2-4-5-7의 순서로 총 4번 이동하여 도달할 수 있으므로 4를 return하면됩니다.

6
0 0 0 0 1 0

위와 같은 입력일 경우에는 1-3-4-6으로 3번만 이동하면 되죠 물론 1-2-3-4-6도 가능하지만 최대 2칸까지 이동할 수있으므로 1-3-4-6의경우가 더 짧게 이동하기 때문에 3이 정답이 됩니다. 

이를 구현한 코드를 먼저 보시겠습니다.

int jumpingOnClouds(vector<int> c) {
    
    int wayCount = 0;    
    for(int i=0; i<(int)(c.size())-1; i++){
        
        if(i<(int)(c.size())-2 && c.at(i+2)==0){
            wayCount++; 
            i++;
        }
        else if(c.at(i+1)==0) wayCount++;                    
    }    
    return wayCount;
}

제가 생각한 방법은 현재위치에서 2칸 앞에 만약 0이 있다면 1칸앞 값은 0과 1에 관계없이 바로 2번째 칸으로 이동할 수 있기 때문에 다음과 같이 바로 2번째 칸으로 넘어 갔습니다. 이때 array 끝에서 2번째 칸보다 큰 곳에서 해당 if문을 돌리면 segmentation fault 가 나오기 때문에 예외 처리를 하였습니다.

 if(i<(int)(c.size())-2 && c.at(i+2)==0){
            wayCount++; 
            i++;
 }

그 후에 else if를 통해서 2칸앞은 0이아니고 1칸앞이 1일경우 한칸앞으로 이동하도록 하였습니다.

else if(c.at(i+1)==0) wayCount++;         

제출한뒤 leader board를 통해 확인한 solution중에 괜찮은 정답이 있어서 올려놓도록 하겠습니다.

    for(int i=2; i<=n; i++) {
        if(A[i] == 0) dp[i] = min(dp[i-1], dp[i-2]) + 1;
        else dp[i] = inf;
    }

그럼 계속해서 다음 문제를 풀어보도록 하겠습니다.