7-W [2342] 문제 풀이 질문입니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-W

작성

328

수정됨

강사님 안녕하세요,

7-W 문제 조건 중에 최초 0,0 위치를 제외하고는 양발이 같은 위치에 있을 수 없다고 되어있는데요.

풀이를 보면 왼발을 움직인 경우/오른발을 움직인 경우 각각에 대해서 min 값을 취하긴 하지만, 위에 말씀드린 양발이 같은 위치에 있는 경우에 대해 배제하는 조건이 없는 것 같아서요.

현재 상태에 대한 발의 위치를 아래와 같이 나타낸다고 할 때,
(왼발 위치, 오른발 위치)

현재 상태가 (1,2) 이고 다음 밟아야하는 위치가 1 이면

(1,2) 로 그대로 두거나, (1,x) 로 이동하는 경우만 있을 수 있는습니다.

하지만, 풀이의 solve 함수에서, v[target] = 1 이 되니까,
int left 의 경우에는 이므로 (1,2) 그대로 있지만,
int right 의 경우에는 (1,1) 에 대해 solve 함수가 호출되지 않을까 생각이 됩니다.

어쨋든 움직이지 않는 경우 (1,2) 가 노력이 덜 들어가므로 left 가 선택이 되었을 것으로 추측이 되지만, (1,1) 로 흘러들어간 DFS 가 이후에 어떤 값을 내보낼지 알수가 없을 것 같아서요

문제는 통과했지만, 양발이 같은 위치에 들어오는 경우는 배제해야하지 않을까요?

제 코드는 다음과 같습니다.

http://boj.kr/8617c099286e4650b615631a7d5974cb

c++코딩-테스트

답변 2

Park SungEun

저도 큰돌님 해설 코드에 같은 의문점이 있었는데,

결국 같은 발이 가는 경우도 체크하게 되지만, 어짜피

최적해를 찾는 과정에서 해당 부분은 절대 답이 될 수 없다는 말씀으로 이해가 되는데

맞게 이해한걸까요?!

큰돌

지식공유자

안녕하세요 Kyoung님 ㅎㅎ

자 이부분을 볼까요?

  if (pos_list[idx] == curr.L || pos_list[idx] == curr.R) // 이미 다음 위치에 이미 발이 올라가 있는 경우
    ret = DFS(curr, idx + 1) + 1;                         // 움직이지 않기
  else                                                    // 왼쪽발 or 오른쪽발을 다음 위치에 반드시 이동

지금 보시는 것처럼 만약 둘 중에 하나가 발에 올라가 있는 경우 그냥 움직이지 않고 DFS를 진행합니다.

즉, 양발이 올라가는 경우는 발생되지 않습니다.

예를 들어

왼, 위 이렇게 위치했다 라고 했을 때 그 다음 왼이 떴을 때 "움직이지 않습니다. "

>> 수강생님이 말씀하신 배제하는 조건이 없어도 그런 조건이 발생되지 않게 코드를 구축하셨기 때문에 신경을 쓰지 않아도 됩니다

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

Kyoung Jun Kim

질문자

강사님 안녕하세요!

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

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

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

문제 풀이 코드 중 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번째 위에서 왼발 오른발 : 모두 위로 두발 모두 가는 경우의 수

왼발 : 위

오른발 : 아래

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

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

좋은 질문 감사합니다.

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

7-W [2342] 문제 풀이 질문입니다.