cjswo8219   9달 전

출발지, 도착지 강둑을 모두 고려해야하나요?
그렇게 되면 1111 예제도 NO가 되는데...

아니면 출발지에 있는 강둑의 상황만 고려해야하는 건가요?


저는 출발지에 있는 강둑의 상황만 고려했고,
양만 조심하면 되겠다 생각했습니다.

그래서 양을 그리디하게 옮기는데

양을 모두 보트에 태웠을 경우와

양이 일부 출발지 강둑에 남아있을 때를 고려했고 

만약 양이 일부 출발지 강둑에 남아있을 때 늑대나 양배추가 남아있다면 실패하는 것으로 조건식을 세웠습니다.

(사실 while 문이 필요없을 수도 있을 것 같긴해요!)

근데 왜 틀렸는지 도무지 이해가안갑니다..

cayley   9달 전

John이 없는 쪽의 상황을 고려해야 합니다.

John이 감시하지 않을 때만 서로 잡아먹는다고 했기 때문에, 양을 싣고 출발지를 떠나면 이 때는 출발지를 고려해야 하고,

John이 출발지로 다시 돌아올 때는 도착지를 고려해야 합니다.

tkvl94   9달 전

양쪽다 고려해야할겁니다.
젤 중요한건 윗분이 말씀하신 것 처럼 존이 유무.

초기
A쪽 현황 (늑대1,양1,양배추1)

B쪽 현환(늑대 0,양0,양배추0)

1. 존이 A -> B로 간다. (양1)

A쪽 현황 (늑대1,양0,양배추1)

B쪽 현황(늑대 0,양1,양배추0)

2. B->A(빈배)

A쪽 현황 (늑대1,양0,양배추1)

B쪽 현황(늑대 0,양1,양배추0)

3. A->B(양배추1)

A쪽 현황(늑대1,양0,양배추0)

B쪽 현황(늑대 0,양1,양배추1)

3. B->A(양1)

A쪽 현황 (늑대1,양1,양배추0)

B쪽 현황(늑대 0,양0,양배추1)

4. A->B(늑대1)

A쪽 현황 (늑대 0,양1,양배추0)

B쪽 현황(늑대 1,양0,양배추1)

5. B->A(빈배)

A쪽 현황 (늑대 0,양1,양배추0)

B쪽 현황(늑대 1,양0,양배추1)

6. A->B(양)

A쪽 현황 (늑대0,양0,양배추0)

B쪽 현황(늑대 1,양1,양배추1)

이런 방식으로 이동이 가능해지는 걸로 생각됩니다.

cjswo8219   9달 전

아래 주석과 같은 논리로 풀었는데
왜 틀렸는지 모르겠습니다..ㅠㅠ

cayley   9달 전

1. S == K 인 경우

다음과 같은 행동이 가능합니다.

(예시: S = 3, W = 4, C = 2, K = 3. 볼드 처리한 부분이 John이 있는 곳입니다.)

  • 초기 상태
    S S S W W W W C C / (없음)

  • 양 K마리를 모두 싣고 도착지에 내려놓는다.
    W W W W C C / S S S

  • 빈 배를 타고 돌아온다.
    W W W W C C / S S S

  • 돌아와서 늑대+양배추 중 K만큼을 싣고 도착지에 내려놓는다.
    W W W / S S S W C C

  • 도착지에 있던 양 K마리를 다시 출발지로 보낸다.
    W W W S S S / W C C

  • 출발지에 남은 늑대+양배추를 도착지로 보낸다.
    S S S / W W W W C C

  • 빈 배를 타고 돌아온다.
    S S S / W W W W C C

  • 출발지에 있는 양을 보낸다.
    (없음) / S S S W W W W C C

이 행동은 어떤 조건에서 가능한지 생각해보시면 좋을 것 같습니다.


2. W+C 와 S는 대칭 관계로, 둘의 자리를 바꿔도 사실상 상황이 같습니다.

(즉, 1번에서 언급한 상황은 W+C == K일 때도 동일하게 적용됩니다.)

그리고 W,C는 분리해서 생각할 필요가 없습니다. 양배추와 늑대는 역할이 완전히 같기 때문입니다.

그렇기 때문에 41라인의 조건처럼 W와 C의 수를 따로따로 생각할 필요가 없고, W+C를 하나로 생각하는 것이 편합니다.

cjswo8219   9달 전

말씀해주신 1번 상황을 고려했을 때, 

W + C 가 <= 2K라면 YES라고 생각해서 다음과 같이 코드를 수정했음에도 실패입니다..

W + C 가 2K보다 큰 경우에는

무조건 양과 늑대 or 양과 양배추가 남아서 실패합니다..

제가 잘못 생각한 부분이 뭔지 궁금합니다...

cayley   9달 전

S < K, S == K 일 때는 문제 없어 보이는데,

S > K 일 때의 조건을 바꾸어야 합니다.


S와 W+C는 대칭적이므로, 둘의 자리를 바꾸어도 사실상 같은 상황이 됩니다.

S < K 일 때 무조건 YES가 되니, W+C < K 여도 무조건 YES가 된다고 할 수 있습니다.

S == K 일 때는 (W+C) <= 2 * K 여야 YES가 되니, W+C == K 일 때는 S <= 2 * K 여야 YES가 됩니다.


위 내용을 토대로 S > K인 경우 중 다음 세 가지 경우에 대해 생각해 보시면 될 것 같습니다!

1. W+C < K 인 경우

2. W+C == K 인 경우

3. W+C > K 인 경우

댓글을 작성하려면 로그인해야 합니다.