글 읽기 - [파이썬] 반례가 있나요?

tkddnjs1234 1년 전 1

아래와 같이 DP로 구현하였습니다.

예제는 통과가 되는데 채점하자 마자 틀렸습니다가 나옵니다.

5 3

3 2

2 6

6 3

위 예제도 정답인 99가 나오고,

2 3

위와 같이 1개의 행렬이 주어진 경우에도 0을 제대로 출력합니다.

어디가 틀린건가요?

# https://www.acmicpc.net/problem/11049

n = int(input())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a,b))
dp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(1,n):
    for i in range(n-k):
        x, y = i, i+k
        dp[x][y] = min(dp[x][y-1]+arr[x][0]*arr[y][0]*arr[y][1], dp[x+1][y]+arr[x][0]*arr[x][1]*arr[y][1])

print(dp[0][-1])

zenith82114 1년 전 8

반례입니다.

tkddnjs1234 1년 전 0

저거 넣고서 돌려보니 알았어요 어디가 틀렸는지 ㅎㅎ

다시 한 번 감사합니다!!

iii719 1년 전 7

다른분들도 저처럼 시간 낭비할까봐 올립니다...

5 3

3 2

2 6

6 3

위 예제의 정답은 99가 아닌 96이 맞습니다 ㅠㅠ

dongwanpianist 6달 전 1

저 역시 이 질문글에서 99가 정답이라는 것을 보고 테스트하며 많은 혼란을 겪었습니다.

질문자께서 작성하신 파이썬 코드로는 말씀하신 대로 99가 나왔는데, 이는 오답입니다. 누가 99를 정답이라고 하였던가요? 스스로 직접 정답이라고 믿고 싶으셨을 수도 있어요.

질문 작성자님 ( @tkddnjs1234 ) 께서
"정답인 99가 나오고"라는 대목에서 최소한 "정답인"이라는 단어를 빼고, 추가적으로 99가 오답임을 명시하여

직접 수정해주셨으면 좋겠습니다.

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

문제

문제

출처

ICPC

[파이썬] 반례가 있나요?

tkddnjs1234 1년 전 1

zenith82114 1년 전 8

tkddnjs1234 1년 전 0

iii719 1년 전 7

dongwanpianist 6달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말