글 읽기 - 0번 자리에 발을 계속 머무르게 하면 안된다는 설명이 빠져있는 것 같습니다.

smilu2245 3년 전 0

2번 동작 수행 후에도, 어느 한 발이 계속 0번 자리에 머무르게 되면 오답이 되는 것 같습니다.

"2번째 지시 사항 이후에도 0번 자리에 발이 머무르는 것은 금지된다."

와 같은 문구가 추가되어야 할 것 같습니다.

제시된 조건을 고려하여 푼 소스

https://www.acmicpc.net/source/19980577

제시된 조건을 배제하고 푼 소스

https://www.acmicpc.net/source/19980687

#include <bits/stdc++.h>
using namespace std;

const int cost[5][5] = {
  {1,2,2,2,2},
  {2,1,3,4,3},
  {2,3,1,3,4},
  {2,4,3,1,3},
  {2,3,4,3,1},
};
const int inf = 0x3f3f3f3f;

int n;
int f[100010];
int dp[100010][5][5];

int get_dp(int i, int a, int b) {
  if (i == -1) {
    if (a == 0 && b == 0) return 0;
    return inf;
  }
  //////////////////////////////////////////////////////////
  // 바로 아래 한 줄을 넣었더니 바로 통과되었습니다.
  //////////////////////////////////////////////////////////    
  if (i >= 2 && (a == 0 || b == 0)) return inf;
  if (a == b) return inf;
  if (a != f[i] && b != f[i]) return inf;
  int &ret = dp[i][a][b];
  if (ret != -1) return ret;
  ret = inf;
  for (int p = 0; p < 5; p++) {
    ret = min(ret, get_dp(i-1, p, b) + cost[p][a]);
    ret = min(ret, get_dp(i-1, a, p) + cost[p][b]);
  }
  return ret;
}

int main(void)
{
  memset(dp, 0xff, sizeof(dp));
  while (1) {
    int tmp; scanf("%d", &tmp);
    if (tmp == 0) break;
    f[n++] = tmp;
  }
  int ans = inf;
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      ans = min(ans, get_dp(n-1, i, j));
    }
  }
  printf("%d\n", ans);
}

djm03178 3년 전 2

그렇지는 않은 것 같습니다. 그런 조건이 있는 거라면 http://boj.kr/9d8a2fda743543ac... 이 코드는 2번째 이후에 한 발이 0에 있는 경우도 고려하는데 통과될 뿐더러, 그렇게 해야 최적이 되는 케이스인 4 4 4 0을 넣었을 때 4가 출력됩니다. 오히려 질문글의 코드는 이때 5를 출력하고, 저 줄을 지워야 4가 나오네요.

해당 줄을 지웠을 때 오답이 되는 것은 그 코드가 '중간에 어느 칸에서 가운데로 움직이는 것을 허용'하기 때문인 것으로 보입니다. p[0..4][0]들을 전부 inf로만 바꾸어주면 그 줄을 지워도 맞습니다.

오히려 4 4 4 0같은 케이스를 추가해서 해당 줄이 있는 코드를 틀리게 해야 할 듯 합니다.

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

문제

문제

출처

ICPC

0번 자리에 발을 계속 머무르게 하면 안된다는 설명이 빠져있는 것 같습니다.

smilu2245 3년 전 0

djm03178 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말