vc0612   3년 전

문제 중에


맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 



란 말이 있는데,


실제 출력 하라는것은, 최대가 되는 경로가 아니라, 최대가 될떄 그 최댓값을 출력하라고 하거든요.


이부분에서 최대가 되는 경로가 아니라, 최대가 될때, 그 최댓값이라고 바꾸는게 맞지 않을까 싶습니다.

gallopsys   3년 전

최대가 될 때, 그 최대값을 출력하라는 문제가 되어버리면 DP의 성질보다는 그리디의 성격을 띄지 않을까 싶습니다.

다시 말해 최대가 될 때 최대값을 출력하라는 문제가 되어 버리면, 문제를 푸는 사람 입장에서는 그 아래 수 중에서 "최대값을 고르라는 의미"인 건지, 아니면 자신이 걸어온 길에서 "최대가 되도록 만드는 값"을 찾으라는 문제인지 애매해져버리기 때문입니다.

예제로 나온 테스트 케이스에서도 보면, 다음과 같은 경로로 최대값이 구성되는 걸 확인할 수가 있죠. 자세히 보면 엄연히 경로를 이루게 됩니다.

       7
     3 8
   8 1 0
 2 7 4 4
4 5 2 6 5


하지만 말씀하신대로 본문을 그렇게 수정해버리면 더 이상 경로를 따르지 않고, 그 아래수 중 가장 큰 수를 선택하는 그리디 문제가 되어버리니까 문제가 될 수도 있죠. 사실상 경로라는 말이 없게 되면 저렇게 문제를 풀 수 있게끔 설명할 길도 없다고 봅니다.

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