글 읽기 - 14738번 런타임 에러 원인이 궁금합니다

bupjae 6년 전 0

이 답안에서 사용한 언어는 octave (거칠게 이야기하면 MATLAB의 open source 구현체) 입니다.

https://en.wikipedia.org/wiki/Absorbing_Markov_chain에 설명한 방법대로 행렬 Q를 만든 뒤 N = (I - Q)^-1 를 하고 1열(시작점)의 모든 요소를 더했습니다.

행렬 Q를 만들 때 index 배정은 초기 상태인 "보드의 바깥"은 포함, N은 제외, 뱀 또는 사다리의 시작점은 제외하고 1부터 순서대로 배정했습니다.

행렬의 역행렬이 존재하지 않을 때에는 Absorbing Markov chain 의 조건인 "어느 칸에 말이 놓여 있든 도착점까지 가는 방법이 존재해야 한다"을 위반하는 경우이기 때문에 -1을 출력합니다.

이 답안이 런타임 에러를 내뱉고 있는데 어디서 틀렸는지 알고싶습니다.

[n, m, s] = scanf("%d%d%d", "C");
z = 1:n+1;
y = zeros(1, n+1);
mm = 1/m;
for i=1:s
  [a, b] = scanf("%d%d", "C");
  z(a+1) = b+1;
endfor
p = z(z == 1:n+1);
for i=1:length(p)
  y(p(i)) = i;
endfor

Q = zeros(length(p)-1);
for i=1:length(p)-1
  for j=1:m
    k = p(i)+j;
    if k <= n && z(k) <= n
      Q(i, y(z(k))) += mm;
    endif
  endfor
endfor
[N, cond] = inv(eye(length(p)-1)-Q);

if cond == 0
  printf("-1");
else
  printf("%.10f", sum(N(1, :)));
endif

bupjae 6년 전 0

재채점 이후 이 답안이 "런타임 에러"에서 "틀렸습니다"로 바뀌었습니다.

아무래도 정확도 관련 문제인 것 같으니 (특히 역행렬 연산은 정확도가 매우 떨어지는 걸로 악명이 높음) 스스로 좀 더 살펴보겠습니다.

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

문제

문제

출처

ICPC

14738번 런타임 에러 원인이 궁금합니다

bupjae 6년 전 0

bupjae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말