liging   1년 전

"사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다."

문제는 이렇게 설명하고 있습니다.


그래서 저는 다음과 같은 방식으로 풀었습니다.

1. 중복된 Coin을 제거하면서 정렬하고자 treeset 이용 - acmicpc.net/source/97374758
2. 그냥 배열에 전부 집어넣기 (중복 제거 X) - acmicpc.net/submit/2293/97374943

이 상황에서 다음 입력 값을 넣으면

[입력]
4 10
1
2
2
5

(1)번 풀이는 "10"
(2)번 풀이는 "28"
을 출력합니다.
근데 두 코드 모두 맞았습니다로 처리됩니다.

제가 이해한 바로는 무한 배낭 문제로 1번 풀이가 맞다고 생각이 드는데, 그걸 떠나서 같은 입력에 대해서 다른 출력을 뱉는데 맞았습니다가 나와서 의문이었습니다.

kidw0124   1년 전

문제 지문의 첫 번째 줄에 "각각의 동전이 나타내는 가치는 다르다."라는 서술이 있습니다.

그래서 문제에 들어있는 데이터에는 제시해주신 입력과 같이 중복되는(적어주신 입력은 2가 중복됩니다) 가치는 주어지지 않습니다.

따라서 중복을 제거한/제거하지 않은 코드 두개는 문제의 올바른 입력에 대해 다른 동작을 하지 않고 둘다 맞았습니다 가 나오게 됩니다.

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