인프런 커뮤니티 질문&답변

강사님 안녕하세요!

제가 질문을 조금 헛갈리게 드린 것 같습니다.

말씀하신대로 제 코드는 왼발/오른발 같은 방향에 위치하는 경우는 없도록 구현을 했구요.

위 질문은 문제 풀이 하신 코드에 대한 질문이었습니다.

문제 풀이 코드 중 solve 함수에서는 왼발/오른발 같은 방향에 위치하는 경우에 대해서도
solve 함수로 호출이 될 것으로 생각 되어서 질문을 드린 것입니다.

int solve(int y, int x, int target){
    if(target == n) return 0;
    if(dp[y][x][target] != -1) return dp[y][x][target];

    int left = solve(v[target], x, target + 1) +check(y, v[target]);
    int right = solve(y, v[target], target + 1) + check(x, v[target]);
    return dp[y][x][target] = min(left,right);
}

아... 그럴수도 있지만 어차피 최적해를 모으는 dp 값에서 제외 됩니다.

int check(int from, int to){
    //처음에는 2
    if(from == 0) return 2;
    //다시 누르면 1
    if(from == to) return 1;
    //반대일 경우
    if(abs(from - to) == 2) return 4;
    //인접할 경우
    return 3;
}

지금 보시면 같을 경우에는 1이고 이 때가 최솟값입니다.

여기서

예를 들어

왼발 : 위

오른발 : 아래

이렇게 되어있을 때 그 다음에 위가 나타났을 때 왼발을 다시 누르는게 최적해입니다. 갑자기 오른발이 위로 같이 올라갈 수도 있다고 생각하지만 그렇게 했을 때

그 다음 아래, 오른쪽, 왼쪽 이런게 나타났을 때 아래가 나타났을때 오른발을 다시 누르는게 최적해이기 때문에 해당 경우의 수는 제외가 됩니다.

물론 어찌하다보면 양발의 경우의 수가 포함될 수도 있지만 어차피 최적해를 모으는 과정에서 제외 또는 중복되서 들어가고 최적해 값에는 영향을 미치지 않기 때문에 상관이 없다고 보시면 됩니다.

예를 들어

위 >> 아래 >> 위 >> 위 이렇게 나온다고 하더라도

경우의 수는

3번째 위에서 왼발 오른발 : 모두 위로 두발 모두 가는 경우의 수

&

왼발 : 위

오른발 : 아래

를 유지하는 경우의 수 둘 다 들어가지만

값은 같기 때문에 원하는 값에 수렴하게 됩니다.

좋은 질문 감사합니다.